Maximum Sum of a Contiguous Subarray

Posted on | In ,

Definition

The maximum subarray problem asks for the contiguous subarray of an array whose sum is the largest.

Solutions

Naive Solution

The brute-force approach tries all $O(n^2)$ subarrays, each taking up to $O(n)$ to compute. This gives a total time of $O(n^3)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;

int mscs(int array[], int n){
    int max = 0;
    for(int i = 0; i < n; ++i){
        for(int j = i; j < n; ++j){
            int sum = 0;
            for(int k = i; k <= j; ++k){
                sum += array[k];
            }
            if(sum > max)
                max = sum;
        }
    }
    return max;
}


int main(){
    int array[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << mscs(array, sizeof(array)/sizeof(int)) << endl;
}

Divide and Conquer

Divide and conquer also applies here. At each recursive level, we must consider subarrays crossing the midpoint, which takes $O(n)$. This gives $T(n) = 2T(n/2) + O(n)$, which by the Master’s Theorem yields $O(n \log n)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
using namespace std;

int mscs(int array[], int f, int t){
    if(f + 1 == t){
        return max(array[f], 0);
    }
    int mid = (f + t)/2;
    int leftMax = mscs(array, f, mid);
    int rightMax = mscs(array, mid, t);
    int leftMiddleMax = 0;
    int rightMiddleMax = 0;
    int temp = 0;
    for(int i = mid; i >= f; --i){
        temp += array[i];
        if(leftMiddleMax < temp){
            leftMiddleMax = temp;
        }
    }
    temp = 0;
    for(int i = mid + 1; i < t; ++i){
        temp += array[i];
        if(rightMiddleMax < temp){
            rightMiddleMax = temp;
        }
    }
    return max(max(leftMax, rightMax), leftMiddleMax + rightMiddleMax);
}

int mscs(int array[], int n){
    return mscs(array, 0, n);
}

int main(){
    int array[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << mscs(array, sizeof(array)/sizeof(int)) << endl;
}

Dynamic Programming

Prefix Sum

The problem can be reformulated: if the answer is $\sum\limits_{k=x}^{y} a_k$, then it equals the difference of two prefix sums: $\sum\limits_{k=1}^{y} a_k - \sum\limits_{k=1}^{x-1} a_k$. So it suffices to find the maximum difference in the prefix sum array, which is straightforward. The code below avoids storing the full prefix sum array to save space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;

int mscs(int array[], int n){
    int prefix_i = array[0];
    int min = prefix_i;
    int sol = max(prefix_i, 0);
    for(int i = 0; i < n; ++i){
        prefix_i += array[i];
        if(min > prefix_i){
            min = prefix_i;
        }
        if(sol < prefix_i - min){
            sol = prefix_i - min;
        }
    }
    return sol;
}


int main(){
    int array[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << mscs(array, sizeof(array)/sizeof(int)) << endl;
}

Max Ends At (Kadane’s Algorithm)

Alternatively, we compute the maximum subarray sum ending at each position $i$. The key observation is that extending the subarray to include the previous element is worthwhile only if the running sum is positive.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;

int mscs(int array[], int n){
    int maxEnds_i = max(0, array[0]);
    int sol = maxEnds_i;
    for(int i = 1; i < n; ++i){
        maxEnds_i = max(maxEnds_i + array[i], 0);
        sol = max(sol, maxEnds_i);
    }
    return sol;
}


int main(){
    int array[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << mscs(array, sizeof(array)/sizeof(int)) << endl;
}