C++

# Maximum Sub-Array Problem in C++

Maximum Sub-Array Problem is the same as Maximum Slice Problem. This tutorial discusses the problem with coding in C++. The question is: what is the maximum sum of any possible sequence of consecutive numbers within an array? This can mean the whole array. This problem and its solution in any language, is referred to as the Maximum Sub-Array Problem. The array can have possible negative numbers.

The solution has to be efficient. It needs to have the fastest time complexity. As of now, the fastest algorithm for the solution is known in the scientific community as Kadane’s Algorithm. This article explains Kadane’s algorithm with C++.

## Data Examples

Consider the following vector (array):

vector<int> A = {5, -7, 3, 5, -2, 4, -1};

The slice (sub-array) with the maximum sum is the sequence, {3, 5, -2, 4}, which gives a sum of 10. No other possible sequence, even the whole array, will give a sum of up to the value of 10. The whole array gives a sum of 7, which is not the maximum sum.

Consider the following vector:

vector<int> B = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

The slice (sub-array) with the maximum sum is the sequence, {4, −1, 2, 1} which gives a sum of 6. Note that there can be negative numbers within the sub-array for maximum sum.

Consider the following vector:

vector<int> C = {3, 2, -6, 4, 0};

The slice (sub-array) with the maximum sum is the sequence, {3, 2} which gives a sum of 5.

Consider the following vector:

vector<int> D = {3, 2, 6, -1, 4, 5, -1, 2};

The sub-array with the maximum sum is the sequence, {3, 2, 6, -1, 4, 5, -1, 2} which gives a sum of 20. It is the whole array.

Consider the following vector:

vector<int> E = {5, 7, -4, -10, -6, 6, 5, 10, -5, 15, 4, -8, -15, -22};

There are two sub-arrays with maximum sums, here. The higher sum is the one that is considered as solution (answer) for the maximum sub-array problem. The sub-arrays are: {5, 7} with a sum of 12, and {6, 5, 10, -5, 15, 4} with a sum of 35. Of course, the slice with the sum of 35, is the answer.

Consider the following vector:

vector<int> F = {-4, 10, 15, 9, -5, -20, -3, -12, -3, 4, 6, 3, 2, 8, 3, -5, -2};

There are two sub-arrays with maximum sums. The higher sum is the one that is considered as solution for the maximum sub-array problem. The sub-arrays are: {10, 15, 9} with a sum of 34, and {4, 6, 3, 2, 8, 3} with a sum of 26. Of course, the slice with the sum of 34 is the answer because the problem is to look for the sub-array with the highest sum and not the sub-array with the higher sum.

The information in this section of the tutorial is not the original work from Kadane. It is the author’s own way to teach Kadane’s algorithm. One of the above vectors, with its running totals, is in this table:

 Data 5 7 -4 -10 -6 6 5 10 -5 15 4 -8 -15 -22 Running Total 5 12 8 -2 -8 -2 3 13 8 23 27 21 16 -6 index 0 1 2 3 4 5 6 7 8 9 10 11 12 13

Running Total for an index is the sum of all the previous values including that for the index. There are two sequences with maximum sums here. They are {5, 7}, which gives a sum of 12, and {6, 5, 10, -5, 15, 4}, which gives a sum of 35. The sequence that gives a sum of 35 is what is desired.

Notice that for the running totals, there are two peaks which are the values, 12 and 27. These  peaks correspond to the last indexes of the two sequences.

So, the idea of Kadane’s algorithm is to be doing the running total while comparing the maximum sums as they are encountered, moving from left to right in the given array.

Another vector from above, with its running totals, is in this table:

There are two sequences with maximum sums. They are {10, 15, 9}, which gives a sum of 34; and {4, 6, 3, 2, 8, 3} which gives a sum of 26. The sequence that gives the sum of 34, is what is desired.

Notice that for the running totals, there are two peaks which are the values, 30 and 13. These peaks correspond to the last indexes of the two sequences.

Again, the idea of Kadane’s algorithm is to be doing the running total while comparing the maximum sums as they are encountered, moving from left to right in the given array.

## Code by Kadane’s Algorithm in C++

The code given in this section of the article is not necessarily what Kadane used. However, it is by his algorithm. The program like many other C++ programs, would begin with:

#include <iostream>
#include<vector>

using namespace std;

There is inclusion of the iostream library, which is responsible for input and output. The standard namespace is used.

The idea of Kadane’s algorithm is to be having the running total while comparing the maximum sums as they are encountered, moving from left to right in the given array. The function for the algorithm is:

int maxSunArray(vector<int> &A) {
int N = A.size();

int maxSum = A[0];
int runTotal = A[0];

for (int i=1; i < N; i++) {
int tempRunTotal = runTotal + A[i];  //could be smaller than A[i]
if (A[i] > tempRunTotal)
runTotal = A[i];  //in case A[i] is bigger than running total
else
runTotal = tempRunTotal;

if (runTotal > maxSum)  //comparing all the maximum sums
maxSum = runTotal;
}

return maxSum;
}

The size, N of the given array (vector) is determined. The variable, maxSum is one of the possible maximum sums. An array has at least one maximum sum. The variable, runTotal represents the running total at each index. They are both initialized with the first value of the array. In this algorithm, if the next value in the array is greater than the running total then that next value will become the new running total.

There is one main for-loop. Scanning begins from 1 and not zero because of the initialization of the variables, maxSum and runTotal to A[0] which the first element of the given array.

In the for-loop, the first statement determines a temporary running total by adding the current value to the accumulated sum of all the previous values.

Next, there is an if/else construct. If the current value alone is greater than the running total so far, then that single value becomes the running total. This is handy especially if all the values in the given array are negative. In this case, the highest negative value alone will become the maximum value (the answer). If the current value alone is not greater than the temporary running total so far, then the running total becomes the previous running total plus the current value, – this the else-part of the if/else construct.

The last code segment in the for-loop chooses between any previous maximum sum for a previous sequence (sub-array) and any current  maximum sum for a current sequence. The higher value is therefore chosen. There can be more than one maximum sub-array sum. Note that the running total would rise and fall, as the array is scanned from left to right. It falls as it meets negative values.

The final chosen maximum sub-array sum is returned after the for-loop.

The content for a suitable C++ main function, for the Kadane’s algorithm function is:

vector<int> A = {5, -7, 3, 5, -2, 4, -1};  //  {3, 5, -2, 4} -> 10
int ret1 = maxSunArray(A);
cout << ret1 << endl;

vector<int> B = {-2, 1, -3, 4, -1, 2, 1, -5, 4};  //  {4, −1, 2, 1} -> 6
int ret2 = maxSunArray(B);
cout << ret2 << endl;

vector<int> C = {3, 2, -6, 4, 0};  //{3, 2} -> 5
int ret3 = maxSunArray(C);
cout << ret3 << endl;

vector<int> D = {3, 2, 6, -1, 4, 5, -1, 2};  //{3, 2, 6, -1, 4, 5, -1, 2} -> 5
int ret4 = maxSunArray(D);
cout << ret4 << endl;

vector<int> E = {5, 7, -4, -10, -6, 6, 5, 10, -5, 15, 4, -8, -15, -22};  // {6, 5, 10, -5, 15, 4}->35
int ret5 = maxSunArray(E);
cout << ret5 << endl;

vector<int> F = {-4, 10, 15, 9, -5, -20, -3, -12, -3, 4, 6, 3, 2, 8, 3, -5, -2};  // {10, 15, 9}->34
int ret6 = maxSunArray(F);
cout << ret6 << endl;

With that, the output will be:

10

6

5

20

35

34

Each line answer here, corresponds to a given array, in order.

## Conclusion

The time complexity for Kadane’s algorithm is O(n), where n is the number of elements in the given array. This time complexity is the fastest for the maximum sub-array problem. There are other algorithms that are slower. The idea of Kadane’s algorithm is to be doing the running total, while comparing the maximum sums as they are encountered, moving from left to right in the given array. If the current value alone is greater than the running total so far, then that single value becomes the new running total. Otherwise, the new running total is the previous running total plus the current element, as anticipated, as the given array is scanned.

There can be more than one maximum sum, for different possible sub-arrays. The highest maximum sum, for all the possible sub-arrays, is chosen.

What are the limiting indexes for the range of the chosen maximum sum? – That is discussion for some other time!

Chrys