The maximum subarray · Coding Gym

Solutions

We have two similar tasks:

find the maximum sum of any nonempty subarray
find the maximum sum of any nonempty subsequence

The latter is clearly esier since the elements in a subsequence are not necessarily contiguous. The former is a very classical problem that we’ll deal with in a moment.

To solve the first task, we can sum all the positive elements. This works as long as we have at least one positive (or zero) element.

What if we have all negative values? The max sum is just the biggest value (the one closest to zero).

Here is the idea in Python:

1
2
3
4
5
6
7


def max_sum_subsequence(a, n):
    m = a[0]
    t = 0
    for i from 0 to n-1:
        m = max(m, a[i])
        if a[i] >= 0: t += a[i]
    return (m >= 0 ? t : m)

Here is a similar approach in C++:

1
2
3
4
5
6
7
8


int maxSubSequence(const vector<int>& v)
{
    auto m = *max_element(begin(v), end(v));
    auto s = accumulate(begin(v), end(v), 0, [](int curr, int toSum) { 
               return (toSum>0) ? (curr+toSum) : curr; 
            });
    return m >= 0 ? s : m;
}

Clearly, we might iterate only once but we like showing the patterns which shape the solution.

Just for completeness, the algorithm above is greedy and takes linear time.

Now, we can face with the other - more difficult - task: the maximum sum of any nonempty subarray.

A quadratic solution exists: we run two loops. The outer loop picks the beginning element, the inner loop finds the maximum possible sum with first element picked by outer loop and compares this maximum with the overall maximum. Finally return the overall maximum.

Clearly, we are interested in a better approach.

A simple idea is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far.

Here is some C++ code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


int maxSubArray(const vector<int>& v)
{
    int max_ending_here, max_so_far;
    max_ending_here = max_so_far = v[0];
    for (auto i=1u; i<v.size(); ++i)
    {
        max_ending_here = max(v[i], max_ending_here+v[i]);
        max_so_far = max(max_so_far, max_ending_here);
    }
    return max_so_far;
}

This solution is called as Kadane’s Algorithm and the time complexity is linear. Kadane’s algorithm is usually used to explain the basics of Dynamic Programing that is is one of the problem solving paradigms where we try to find a solution by breaking the larger problem into subproblems.

As Marco Arena noted, Kadane’s algorithm can be rewritten as the combination of two patterns:

prefix sum (with a special binary function)
maximum

So here is a possible C++ alternative (clearly, it does two iterations and changes the original array):

1
2
3
4
5
6
7


int maxSubArray(vector<int>& v)
{
    partial_sum(begin(v), end(v), begin(v), [](int sum, int current){
        return max(current, sum + current);
    });
    return *max_element(begin(v), end(v)); 
}

In C++20 this solution can be implemented elegantly and efficiently (single pass) with ranges:

1
2
3
4


int maxSubArray(vector<int>& v)
{
    return ranges::max(view::partial_sum(v, [](auto m, auto i) { return std::max(m+i, i); }));
}

Not shown here, there is another interesting solution which adopts the Divide and Conquer approach. Find it here.

So, here is a complete solution:

 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


int maxSubArray(vector<int>& v)
{
    partial_sum(begin(v), end(v), begin(v), [](int sum, int current){
        return max(current, sum + current);
    });
    return *max_element(begin(v), end(v)); 
}       

int maxSubSequence(const vector<int>& v)
{
    auto m = *max_element(begin(v), end(v));
    auto s = accumulate(begin(v), end(v), 0, [](int curr, int toSum) { 
               return (toSum>0) ? (curr+toSum) : curr; 
            });
    return m >= 0 ? s : m;
}

int main() 
{
    size_t T;
    cin >> T;
    while (T--)
    {
        size_t size;
        cin >> size;
        vector<int> v; v.reserve(size);
        copy_n(istream_iterator<int>(cin), size, back_inserter(v));
        auto msb = maxSubSequence(v);
        auto msa = maxSubArray(v);
        cout << msa << " " << msb << "\n";
     }    
}

A complete solution is also found on HackerRank:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


for _ in range(input()):
    n = input()
    arr = map(int,raw_input().split())
    max_sum = -999999999
    c_sum = 0
    sum1 = 0
    for i in range(n):
        sum1+=arr[i]
        if arr[i]>0:
            c_sum += arr[i]
        if sum1>max_sum:
            max_sum = sum1
        if sum1<0:
            sum1 = 0
    if c_sum == 0:
        c_sum = max(arr)
    print max_sum,c_sum

This Rust solution accepts empty arrays and gives a None result in that case, because there’s no possible sum and 0 would be the wrong result.

This is not actually needed for this challenge (n > 0 is a constraint).

But in this way we can return an “impossible” result without panicing or just returning zero. A panic can still happen if the sum causes an integer overflow.

 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


fn max_sub_sequence(arr: &[isize]) -> Option<isize> {
    if arr.is_empty() {
        return None;
    }

    let only_neg = arr.iter().all(|&x| x < 0);

    if only_neg {
        arr.iter().max().copied()
    } else {
        Some(arr.iter().filter(|&&x| x > 0).sum())
    }
}

fn max_sub_array(arr: &[isize]) -> Option<isize> {
    let mut e = *arr.get(0)?;
    let mut m = *arr.get(0)?;

    for &x in arr.iter().skip(1) {
        e = (e + x).max(x);
        m = m.max(e);
    }

    Some(m)
}

fn solve(arr: &[isize]) -> (Option<isize>, Option<isize>) {
    (max_sub_array(&arr), max_sub_sequence(&arr))
}

dynamic programming prefix sum