The Maximum Subarray

Given an array A=\{a_1,a_2,\dots,a_N\} of N elements, find the maximum possible sum of a

  1. Contiguous subarray
  2. Non-contiguous (not necessarily contiguous) subarray.

Empty subarrays / subsequences should not be considered.

Problem Source : Hackerrank

Input

First line of the input has an integer T. T cases follow.
Each test case begins with an integer N. In the next line, N integers follow representing the elements of array A.

Output

Two, space separated, integers denoting the maximum contiguous and non-contiguous subarray. At least one integer should be selected and put into the subarrays (this may be required in cases where all elements are negative).

Constraints

  • 1 \leq T \leq 10
  • 1 \leq N \leq 10^5
  • -10^4 \leq a_i \leq 10^4

Sample Input

2 
4 
1 2 3 4
6
2 -1 2 3 4 -5

Sample Output

10 10
10 11

Explanation

In the first case:
The max sum for both contiguous and non-contiguous elements is the sum of ALL the elements (as they are all positive).

In the second case:
[2 -1 2 3 4] –> This forms the contiguous sub-array with the maximum sum.
For the max sum of a not-necessarily-contiguous group of elements, simply add all the positive elements.

Solution

It would be relatively easier if the problem allows an empty subarray. Then, we could simply apply Kadane’s Algorithm, an algorithm to find the maximum subarray with O(n) runtime efficiency.

Pseudocode

tmax = smax = 0
for x in A:
    tmax = max(0 , tmax + x)
    smax = max(tmax , smax)
print smax

Properties of a maximum subarray

  • It’s either empty or consists of elements with positive summation.
  • It only starts and ends with a positive number.
  • The absolute value of the negative number in the maximum subarray is smaller than the sum of elements at its left.

With these properties in hand, the motivation behind Kadane’s Algorithm is clear. tmax looks for all positive contiguous sum of the array till the point x. When tmax is negative, it violates the third property of a maximum subarray. Hence, it starts the sum from 0 again and continue searching for positive contiguous segments. Everytime tmax has a new value, it is compared with smax to check if it’s the largest sum so far.

The problem, however, is that empty array is not allowed. Kadane’s Algorithm returns 0 when all the elements are negatives instead of the largest negative numbers. Fortunately, a slight variation of Kadane’s Algorithm can solve the problem.

tmax = smax = A[0]
for i = 1 to N-1:
    tmax = max(A[i] , tmax + A[i])
    smax = max(smax , tmax)
print smax

In this variation, tmax compares the current element with the contiguous sum. If the contiguous sum is smaller than the current element, it means that the previous contiguous sum is negative, so we only have to pick the current element at the moment. After we iterate through the array, if all of its elements are negatives, smax will return the largest negative element.

The other problem is to find the maximum sum of a non-contiguous subarray. We only have to take the sum of all positive integers in the array. If all of its elements are negatives, return the largest negative element ( Hint : smax ). In the following code, the maximum sum of a non-contiguous subarray is denoted as pmax.

C++

#include <iostream>

using namespace std;

int max(int a, int b){
    return (a > b ? a : b);
}

int A[100001];

int main(){

    int T;
    cin >> T;

    int N, smax, tmax, pmax;
    for (int i=0; i<T; i++){
        cin >> N;
        
        cin >> A[0];
        smax = tmax = A[0]; pmax = max(0, A[0]);
        for (int j=1; j<N; j++){
            cin >> A[j];

            tmax = max(A[j], tmax + A[j]);
            smax = max(smax, tmax);
            pmax += max(0, A[j]);
        }

        cout << smax << " " << (smax < 0 ? smax : pmax);
        cout << endl;
    }

    return 0;
}
Advertisements
The Maximum Subarray

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s