12,299,851 members (55,839 online)
alternative version

17.7K views
Posted

# Maximum Value Contiguous Subsequence

, 14 Dec 2009 Apache
 Rate this:
Given a sequence of n real numbers, determine a contiguous subsequence for which the sum in the subsequence is maximum.

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

## About the Author

 Web Developer United States
No Biography provided

## Comments and Discussions

 First Prev Next
 My vote of 2 Dave Kreskowiak20-Dec-09 7:43 Dave Kreskowiak 20-Dec-09 7:43
 My vote of 2 gaurav_verma_mca15-Dec-09 20:30 gaurav_verma_mca 15-Dec-09 20:30
 And this article in the "Advanced" section because? Rajesh R Subramanian14-Dec-09 21:31 Rajesh R Subramanian 14-Dec-09 21:31
 Last Visit: 31-Dec-99 18:00     Last Update: 29-May-16 0:43 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.