# Maximum Sum Subarray in C++ : More on dynamic programming – 2

Question. We are given an array A of n integers. We wish to find a contiguous subarray of A having the greatest sum.

Solution.

We note first that the required subarray can end at any of the n indexes , 0 through n-1. Hence, let us define $V[k]$ as the value (i.e. sum) of the optimal subarray ending at index k.

Let OPT denote the value of the required optimal subarray.

Therefore, we have that:

$OPT = max_{0 \leq k \leq n-1} V[k]$.

We can compute OPT using the V[k] values in O(n) time.

——-

We now look at computing the V[k] values.

We have the following recurrence:

$V[k]=max(A[k]+V[k-1],A[k])$

(Since the subarray has to end at index $k$, $A[k]$ is always part of it.)

——–

Further, in order to compute the optimal subarray, we need to keep track of the starting index of the subarray. We store the starting index of the optimal subarrays for our subproblems in an array of length n called Index.

———

We can compute the $V$ array and the Index array using the above recurrence in a bottom up manner.

Pseudocode for computing V and Index:

V[0] = A[0];

Index[0] = 0;

For (i going from 1 to n-1)

//Use the above recurrence to compute V[i].

If ( V[i-1] > 0)

V[i] = V[i-1] + A[i];

Index[i] = Index[i-1];

Else

V[i] = A[i];

Index[i] = i;

End of algorithm.

——————————

We can write the above pseudocode in C/ C++ as follows:

// 1. computing the V and Index arrays. (array A of length n is given to us.)

int V[n], Index[n], OPT;

V[0] =A[0];

Index[0] = 0;

for ( int i = 1; i < n; i ++ )

{

//use the recurrence to find V[i] and Index[i].

if ( V[i-1] > 0)

{

V[i] = A[i] + V[i-1];

//starting index of opt. subarray ending at i is Index[i-1].

Index [i] = Index[i-1];

}

else

{

V[i] = A[i];

//starting index of opt subarray ending at i is i itself.

Index[i] = i;

}

}

—————-

// 2. Now, we can compute OPT using V in O(n) time.

OPT = V[0];

int final_index = 0; //final_index will store the ending index of the opt subarray in A.

for (i = 1; i < n; i++)

{

if (V[i] > OPT)

{

OPT = V[i];

final_index = i;

}

}

————–

// 3. We can compute the optimal subarray (the starting and ending indices) from Index.

//ending index is final_index (which we have already computed).

int begin_index = Index[final_index];

———-

That completes our algorithm.

Analysis of the algorithm:

1. Computing V and Index arrays takes O(n) time.

2. Computing OPT and final_index from V takes O(n) time.

3. Computing begin_index from Index takes O(1) time.

————

Advertisements