Maximum Alternating Sum Subsequence
October 8, 2009 Leave a comment
We are given a sequence of positive integers, say
We need to find a subsequence of maximum alternating sum. S = is said to be a subsequence if Alternating sum of subsequence, S is simply .
So, our task is to find a subsequence, say which maximizes the above sum. (Note that there may be more than one such optimal subsequence, .)
Sequence, X = [10, 2, 3, 8, 9, 1, 10] ——-> = [10, 2, 9, 1, 10] (Alternating sum = 10 – 2 + 9 – 1 + 10 = 26.)
Sequence, X = [1, 1, 4, 10, 3, 1, 10, 20] ——-> = [10, 1, 20] (Alternating sum = 29.) (Another possible optimal subsequence is [1, 1, 10, 1, 20].)
1. The length of the optimal subsequence will be odd. (It is quite clear why this is so. If we have an even subsequence, the last term of the subsequence is subtracted in the alternating sum. So, by removing one element from this sequence, we get a sequence of higher alternating sum. [This is true since all elements of the sequence are positive.]. So, for any even subsequence, we can always find an odd subsequence of higher alternating sum.)
Development of the algorithm:
1. Now, how do we get an Odd Subsequence? Simple, by adding one element to an even subsequence. Again, how do we get an Even Subsequence? And again, by adding one element to an Odd Subsequence.
Suppose we want to find an Odd Subsequence of Maximum Alternating Sum (MAS) having its last element as . How do we get that?
Answer: The element prior to in this required Odd Subsequence is an element having index k-1. If it is then we would find an Even Subsequence of MAS ending at and add to that.
How do we decide which would be the index of the element preceding ?
Simple. Consider an Even Subsequence of MAS ending at , and add to that. This is one possibility. What is the Alternating Sum of this Odd Subsequence? Answer: MAS(Even Subsequence ending at
We have to maximize the Alternating Sum of the Odd Subsequence. Therefore, the Odd Subsequence of MAS ending at is precisely one that maximizes: MAS(Even Subsequence ending at ) + over all indices ‘j’ ranging from ‘0’ to ‘k-1’. (Since, is added to each of these sums, we can select an optimal one by taking the one that maximizes MAS(Even Subsequence ending at ). )
Let OPT_Odd (j) denote MAS of Odd Subsequence ending at . Analogously, let OPT_Even (j) denote MAS of Even Subsequence ending at .
(The solution to the problem is given by: OPT_Odd (j). )
Based on the above discussion, we get the following recursion:
OPT_Odd (j) = OPT_Even (i) + .
and, OPT_Even (j) = OPT_Odd (i) + .
Base case values:
OPT_Odd (0) = 0; OPT_Odd (1) =
OPT_Even (0) = 0; OPT_Even (1) = 0.
How the algorithm computes OPT_Odd and OPT_Even values:
It computes OPT_Odd (2) using base values of OPT_Even (0) and OPT_Even (1). Similarly, it computes OPT_Even (2) using base values of OPT_Odd (0) and OPT_Odd (1).
Then, we compute OPT_Odd (3) using OPT_Even values for 0, 1 and 2. Similar is the case with OPT_Even.
We proceed this way until we compute OPT_Odd (n).
As pointed above, the value of the Odd Subsequence of MAS is given by:
Points to ponder:
1. You can try writing the pseudocode for the algorithm, indicating the way it computes the OPT_Odd and OPT_Even values.
2. What is the running time of the implementation of the algorithm given by your pseudocode? Is it
3. The above algorithm computes the Value of the optimal solution. How do we get an Optimal Subsequence itself? You might have to modify the algorithm to keep track of the index of the Even Subsequence that maximizes a particular Odd Subsequence, and also do the same for Even Subsequences. Are there other ways to find an optimal subsequence? (Computing Optimal Solutions (as opposed to optimal value) would be given in any standard textbook on algorithm design. Eg. Kleinberg/Tardos Chap. 6)
(There might be errors in the above algorithm/anlysis. I apologize for them. It would be great if you point out such errors.)