Maximum Alternating Sum Subsequence

October 8, 2009 Leave a comment

We are given a sequence of positive integers, say [x_1, x_2, ..., x_n].

We need to find a subsequence of maximum alternating sum.  S = [x_{i1}, x_{i2}, ..., x_{ik}] is said to be a subsequence if i1 < i2 < ... < ik. Alternating sum of subsequence, S is simply x_{i1} - x_{i2} + x_{i3} - x_{i4} + ... +/- x_{ik}. .

So, our task is to find a subsequence, say S^* which maximizes the above sum. (Note that there may be more than one such optimal subsequence, S^* .)

Example:

Sequence, X = [10, 2, 3, 8, 9, 1, 10] ——->  S^* = [10, 2, 9, 1, 10]  (Alternating sum = 10 – 2 + 9 – 1 + 10 = 26.)

Sequence, X = [1, 1, 4, 10, 3, 1, 10, 20] ——-> S^* = [10, 1, 20] (Alternating sum = 29.) (Another possible optimal subsequence is [1, 1, 10, 1, 20].)

Observation:-

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 x_k . How do we get that?

Answer: The element prior to x_k in this required Odd Subsequence is an element having index \leq k-1. If it is x_{k-3} then we would find an Even Subsequence of MAS ending at x_{k-3} and add x_k to that.

How do we decide which would be the index of the element preceding x_k ?

Simple. Consider an Even Subsequence of MAS ending at x_k-1 , and add x_k to that. This is one possibility. What is the Alternating Sum of this Odd Subsequence? Answer: MAS(Even Subsequence ending at x_{k-1}) + x_k.

We have to maximize the Alternating Sum of the Odd Subsequence. Therefore, the Odd Subsequence of MAS ending at x_k is precisely one that maximizes: MAS(Even Subsequence ending at x_j ) + x_k over all indices ‘j’ ranging from ‘0’ to ‘k-1’. (Since, x_k is added to each of these sums, we can select an optimal one by taking the one that maximizes MAS(Even Subsequence ending at x_j ). )

Notation:

Let OPT_Odd (j) denote MAS of Odd Subsequence ending at x_j . Analogously, let OPT_Even (j) denote MAS of Even Subsequence ending at x_j .

(The solution to the problem is given by: max_{j: '1' \space to 'n'} OPT_Odd (j). )

—–

Based on the above discussion, we get the following recursion:

OPT_Odd (j) = max_{i: '0' \space to 'j-1'} OPT_Even (i) + x_j .

and, OPT_Even (j) = max_{i: '1' \space to 'j-1'} OPT_Odd (i) + x_j .

Base case values:

OPT_Odd (0) = 0; OPT_Odd (1) = x_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:

max_{i: '1' \space to 'n'} OPT_Odd (i).

——-

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 O(n^2)?

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.)

Filed under Theoretical Computer Science Tagged with , ,

Leave a comment