Pokémon Army
Given an array find the subsequence that gives maximum alternate sum.
Alternate sum of A = [5,4,3,2,1] = 5–4+3–2+1
Example :
A = [3,1,5,9,10,4,6,8,7,2] the subsequence that gives maximum would be [3,1,10,4,8]
Solution
Brute force would be to consider adding +/- sign to each index or not have it at all. Therefore each element has 3 possibilities. Which makes the time total solutions to be 3*3*3*….. for an array of size n therefore it is 3^n
You can implement this by simple recursion and further speed it up a little bit by memoisation.
lets call dp(i,+) as the maximum value of subsequence if i was chosen into the subsequence and i was +ve
similarly dp(i,-) as the minimum value of subsequence if i was chosen into the subsequence and i was -ve.
The last one dp(i,/) is maximum value if the subsequence ommited i’th element.
The transition for all these states is whats left out.
solve(i,symbol) will be as follows
dp(i,+) = max(a[i] + dp(j,-)) for all j < i
dp(i,-) = max(-a[i] + dp(j,+)) for all j < i
dp(i,/) = max(dp(j,+),dp(j,-)) for all j < i
if symbol == + return dp(i,+)
if symbol == — return dp(i,-)
if symbol == / return dp(i,/)
call max(solve(n,+),solve(n,-),solve(n,/)) and you have your brute force dp. you can memorize the state solve(i,symbol) for faster execution.
But you can see that this will easily exceed time limit since n is 3*1⁰⁵ and q is also the same . We also need to process q queries. Each query we swap two elements in the array and find the maximum. Therefore we can speculate that the time limit should be log(N) or O(1) to find the maximum alternate sum. We can use this code as a way to verify our logic since this is 100% accurate.
Optimal solution
The ideal situation is when we have N/2 + 1 largest positives and N/2 smallest negatives and N being odd. N should be odd because we will have more positives in that case since our aim is to maximise.
The most ideal ordering for such an array would be
A1 > A2 < A3 > A4 < A5 > A6 < A7 ……
It is enough to select a subsequence that satisfy the above equalities.
Take the example A = [3,1,5,9,10,4,6,8,7,2,10]
we can add -/+ infinity to the edges to satisfy the above condition.
So we pick 3>1<10>4<8 we can pick 2 but the last element will be negative in that case and like we discussed above we want to keep the length of the subsequence odd. If there was another element greater than 2 after, that case we can pick 2 as the last element will be poisitive and will contribute more to the sum therefore maximising it.
Now as for queries you can see that on swapping A[l] and A[r] it affects only A[l-1] , A[l] , A[l+1] and A[r-1], A[r], A[r+1]. Therefore we can remove them from our sub sequence add the ones that suites the new conditions.
You can find my complete notes here
