Given an Array, find the maximum difference between the sum of elements in odd indices and even indices. To achieve this you can delete any number of elements from the array,after deleting the elements,the array will be re-numbered.
Example : 1 4 8 2 6
Upon deleting 1,4.
New array 8 2 6
Answer is 8+6-2 = 12.
Constraints : 1<=N<=1e5
Can anyone please help me solve this problem?
Auto comment: topic has been updated by AjaySabarish (previous revision, new revision, compare).
Auto comment: topic has been updated by AjaySabarish (previous revision, new revision, compare).
Let's say we always add the values at even positions and we always rest the values at odd positions. Now, we will iterate from 1 to $$$n$$$ and make choices: keep the element or delete it; the thing is that when we keep an element, we need to know if it is at an even position or an odd position, so we will do Dynamic Programming:
$$$dp[i][0]$$$: max possible sum using the elements in $$${a_1, a_2, \dots, a_i}$$$ and the resulting array is of even length.
$$$dp[i][1]$$$: same as above, but now the resulting array is of odd length.
Transitions are: keep it or delete it.
$$$dp[i][r] = \max(dp[i-1][r], dp[i-1][!r] + a[i] * ((r == 0)?1:-1)$$$;
Now it's when someone says: Wait minute, you are always adding at even positions and resting at odd positions, what if it's of the other way. Well, for this, perform again the DP but adding at odd positions and resting at even positions. You stay with the maximum of both solutions.