Maximum Value Contiguous Subsequence

Download source code - 3.83 KB

Introduction

This article describes a dynamic programming method to solve the "Maximum value contiguous subsequence problem". The problem is defined as follows: given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i) ... A(j) for which the sum of elements in the subsequence is maximized. Here is an example:

{ -2, 3, -16, 100, -4, 5 }: Answer is: 100,-4,5 which adds to 101.
{ -2, 11, -4, 13, -5, 2 }: Answer is : 11, -4, 13 which adds to 20.
{-15,-23,-476,-3, -292}: Answer is -3 which adds to -3.

Note that this problem is only interesting if the input sequence contains one or more negative numbers; otherwise, the answer is the entire input set.

Background

This problem can be solved using a technique called dynamic programming. The answer is built one step at a time, and at every step, the element under consideration either becomes part of the final answer or a a new sequence is started. At the same time, the running sum is computed and compared to the current maximum. If it is greater than the maximum, then the running sum is the new maximum.

Solution with an example

Let's look at it using an example: { -2, 3, -16, 100, -4, 5 }.

Step 1

We begin with picking the first element as our maximum subsequence; hence, the maximum subsequence starts and ends at index '0' (since arrays start at index 0). Now, the running sum is "-2".

After step 1

Now, we pick the next element 3 and add it to the running sum: 3 + (-2) = 1. This running sum is compared with the element itself and if the element is bigger than the running sum, then we start a new sequence from this position and drop the previous sequence.

If the running sum is greater than 3, then we would have extended the subsequence and made 3 a part of the previous sequence.

Using the code

First, let's define the class that will hold our answer.

The class SequenceResult will contain the final result, including the index and the sum. The restart function starts a new sequence from the specified index and value. The extend function extends the current sequence and adds the current element to the final sum.

/// <summary>
/// The result set containing the starting and ending sequence
/// and the sum of that sequence.
/// </summary>
public class SequenceResult
{
    public int start = -1;
    public int end = -1;
    public int sum = 0;

    /// <summary>
    /// Restart the sequence at the current position.
    /// </summary>
    /// <param name="index"></param>
    /// <param name="value"></param>
    public void restart(int index, int value)
    {
        start = end = index;
        sum = value;
    }

    /// <summary>
    /// Extend the current sequence and add the 'value' to the sum.
    /// </summary>
    /// <param name="value"></param>
    public void extend(int value)
    {
        end++;
        sum += value;
    }

    public override String ToString()
    {
        String str = "sum=" + sum + ", 
          range=(" + start + "," + end + ")";

        return str;
    }

}

Here is the function which finds the maximum value continuous sequence:

/// <summary>
/// Find the maximum subsequence.
/// </summary>
/// <param name="input"></param>
/// <returns></returns>
public static SequenceResult FindMaxValueContigousSeq(int[] input)
{
    SequenceResult curr = new SequenceResult();
    SequenceResult max = new SequenceResult();

    max.restart(0, input[0]);
    curr.restart(0,input[0]);

    for (int i = 1; i < input.Length; i++)
    {
        int sum = input[i] + curr.sum;
        if (input[i] > sum)
        {
            // if the element is greater than the running sum then
            // a new sequence is started from the current element.
            curr.restart(i, input[i]);
        }
        else
        {
            // the current element is part of the sequence.
            curr.extend(input[i]);
        }

        if (curr.sum > max.sum)
        {
            // if the current running sum is greater than
            // the max then it becomes the maximum
            max.copy(curr);
        }
    }
    return max;
}

Points of interest

One thing to keep in mind is that the implementation will fail if the sum of the numbers overflows. The algorithm itself is correct. It is easy to fix the solution by making the sum a 64 bit value instead of 32 bit, which makes it difficult to overflow.