Maximum sum of a contiguous subsequence

Posted on | In

Definition

The maximum sum of a contiguous subsequence problem is a problem that finds a contiguous subarray of an array that sum of it will be a maximum.

Solution

Naive solution

In the naive method, every subarray can be computed as it is. Computing sum of subarray takes at most and there could be possible subarrays. As a result, it takes at most $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 can be applied to this problem either. Notice that to compute optimal solution, the solution that contain middle point should be reconsidered. Therefore, it needs $O(n)$ time for it at each level. As a result, it takses at most $O(n \log n)$. Notice that $T(n) = 2T(n/2) + O(n)$ and it can be applied to Master theorem.

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

Instead of compute the actual problem, this problem can be converted into the smaller problem. Let’s assume that answer is $\sum\limits_{k=x}^{y} a_k$. Then, answer is $\sum\limits_{k=x}^{y} a_k = \sum\limits_{k=1}^{y} a_k - \sum\limits_{k=1}^{x} a_k$. Which means it’s enough to solve maximum difference in the Prefix sum array. Which is much easier to be solved. Notice that to save space, there is no physical Prefix sum array in the code below.

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

Instead of using Prefix sum, algorithm can compute the maximum value that will ends at $i$th elements. In this case, it is obvious that it just decide whether it will expend to the next element or not because advantage of choosing subarray from ahead should be 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;
}