Won’t this approach fail in test case like…
3 2 5 1
the answer should be 35 i guess, but the approach would give 19.
It is a very good editorial indeed… I had solved this problem using the same approach (dp), but used a 2d array. ‘dp[n][2]’.
In my solution,
dp[i][0] --> the highest number we can reach without swapping the ith element
dp[i][1] --> the highest number we can reach when we swap the element(and its a must).
Thus, my answer came upto max(dp[n - 1][0], dp[n - 1][1])
(Got a WA in the first go because of int 
, Then got AC using long long)
1 Like
I am taking difference of arr[i] and arr[i+1] (for 1<=i<=n-1, 1-based indexing) and at the same time storing in a diff list. After which i declared a boolean array of length n (to track pairs which had swapped). After that I sort this diff list in ASC order and iterate through it in reverse order. While iterating in reverse order am considering only those element which is positive and not visited yet.
Link to code is : CodeChef: Practical coding for everyone
Can anybody help me where m going wrong in my logic, bcoz am getting all WA
Why will it? Can you dry run it to show why? 
I am sorry…the approach gives answer 19, but shouldn’t the answer be 35.
Dry Run…(0 based indexing)
3 2 5 1…3rd index
3 2 1 5…0th index
2 3 1 5…2nd index
2 1 3 5
2+22+33+5*4=35
But the approach would give…19
Nice Explanation about how to approach DP problems.
1 Like
In an array of size 4, where there are at most 4*5/2=10 sub-arrays possible, how can answer be more than 10?
Its nice that you share the Intuition on how to arrive on “this” solution. Great Editorial 
1 Like
can anyone give and explain me a test case where Greedy Approach is failing.
What is the greedy approach you are following? Did it pass the TC given in editorial?
if a[i] > a[i+1] && a[i+1] > a[i+2] I’ll check which two elements will contribute more to the sum after swapping and swap elements accordingly.
I think the question asks for a maximum value instead of number of ways.
Riiiight. Got myself confused with something else (DELARRAY) 
Each element can be swapped at most once. Your step of-
2 3 1 5…2nd index
is invalid as both 1 and 3 have already been swapped.
That was elegant and crisp!
1 Like
Can anyone help me find a test case which fails with this code ?
https://www.codechef.com/viewsolution/25923247
Clearly this is a greedy method. This won’t work. So the next option is DP. The editorial is pretty clear. There even is a test case to show exactly where the greedy solution fails.
Try
{105,100,110,1}
1 Like