Maximum sub-array

Given an array, find the contiguous sequence which has the largest sum. The array can contain positive or negative numbers or a combination of positive and negative numbers.

A simple approach is to construct a table representing the sum of all the subproblems. The subproblem with the largest sum is the solution to this problem.

Consider an 'input' array of five integers - {-2, 4, 5, -9, -8}. Construct a table 'Sum' as shown below. Start by initializing the diagonal to the input elements. We are only interested in the half of the matrix above the diagonal. Let us start filling up the rest of the entries.

Going over each of the rows, for each cell add the value corresponding to the column with the value in the previous column of that row.

For example,

	-2	4	5	-9	-8
-2	-2	2	7	-2	-10
4	0	4	9	0	-8
5	0	0	5	-4	-12
-9	0	0	0	-9	-17
-8	0	0	0	0	-8

When filling the first row, the first element -2 has already been filled in as part of the diagonal.

Next the second element is (-2 + 4) = 2 , the third element is (2 + 5) = 7, the fourth element is (7 + -9 ) = -2 and the last element is (-2 + -8) = -10

Repeat similarly for each row independently.

Each cell (i, j) now represents the sum of all numbers start from the i^th element till the j^th element including both of them.

Pick the cell with the maximum value. In this case, it is 9, which is the largest sum of any subarray. In this example, the sub-array with the largest sum is {4, 5}.

The time complexity of this algorithm is O(n^2). It also requires O(n^2) additional space. Here is the C++ code:

int input[5] = {-2, 4, 5, -9, -8};

int SubArrayMaxSum(int n) {

if(n == 0) return 0; //empty array

if(n == 1) return input[0]; //only one element

int sum[n][n];

//initialize the matrix to 0

for(int i = 0; i < n; ++i) {

  for(int j = 0; j < n; ++j) {

    sum[i][j] = 0;

  }

}

//initialize the diagonal elements to the input array

for(int i = 0; i < n; ++i) {

  sum[i][i] = input[i];

}

int max_sum = sum[0][0];

for(int i = 0; i < n; ++i) {

  for(int j = i; j < n; ++j) {

    if(i == 0 && j == 0) continue; //skip

      sum[i][j] = sum[i][j-1] + input[j];

      if(sum[i][j] > max_sum) { //update the maximum sum

        max_sum = sum[i][j];

      }

  }

}

return max_sum;

}

Invoke the function as SubArrayMaxSum(5).

A better approach is to use dynamic programming and memoize the results in an array S. At each index i, we solve a subproblem that corresponds to the the maximum possible sub-array sum ending at i. As we iterate over the array for each element, say at index i, we make a decision if the maximum sub-array sum is got either by expanding the previous best sub-array ending at (i-1) or to start a new sub-array from this element. The value is hence the larger of the two values – current element or the sum of the maximal sub-array ending at the previous element and the current element. The maximum value in this result array represents the largest possible sub-array sum.

S_i = max (S_i-1+input[i], input[i]) and the maximum sub-array sum is

S_max = max (S_i), 0 < i < n

Consider the same example input = {-2, 4, 5, -9, -8}. Construct the array as below. Initially, the sub-array with the largest sum is the first input element.

-2

4

9

0

-8

index 0: initialize to the first input element = -2

index 1: max(-2+4, 4) = 4

index 2: max(4+5, 5) = 9

index 3: max(9-9, -9) = 0

index 4: max(0-8,-8) = -8

S_max = 9, which is the largest possible sub-array sum.

In this method, we will visit all the array values exactly once. The time complexity is O(n). As we are using an additional array, the space complexity is O(n).

Here is the C++ code:

int input[5] = {-2, 4, 5, -9, -8};

int CalculateMaxSubArraySum(int n) {

if(n == 0) return 0; //empty array

if(n == 1) return input[0]; //only one element

int local_sum[n];

local_sum[0] = input[0];

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

  local_sum[i] = 0;

}

int max_sum = input[0];

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

//either include the element to the previous max sub-array

//or start a new max sub-array from here

  local_sum[i] = max(input[i], local_sum[i-1] + input[i]);

  if(max_sum < local_sum[i]) {

    max_sum = local_sum[i];

  }

}

for(int i = 0; i < n; ++i) {

  cout << local_sum[i] << endl;

}

return max_sum;

}

Invoke the function as: CalculateMaxSubArraySum(5).