You are right!! I changed int i to ll i and it worked. I think that was the problem. Either we should change int arr or int i to ll.
It is wrong because you are not considering the case where the previous 2 elements have been swapped( i-1 and i-2 ). You are forcing the elements not to get swapped. This way you will get lesser score than expected
arr[i]*(i-1)
This part in line 72 overflows. If both operands of * are int, then their intermediate result is also stored in int.
Thanks! I got it.
Yeah! I got it. Thanks. Henceforth, I should be careful about datatypes.
1 Like
yes, take long long int:)
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