Maximum Subarray Sum - Hacker Rank Solution

We define the following:

• A subarray of array  of length  is a contiguous segment from  through  where .
• The sum of an array is the sum of its elements.

Given an  element array of integers, , and an integer, , determine the maximum value of the sum of any of its subarrays modulo . For example, Assume  and . The following table lists all subarrays and their moduli:

  sum %2
[1]  1 1
[2]  2 0
[3]  3 1
[1,2]  3 1
[2,3]  5 1
[1,2,3]  6 0

The maximum modulus is .

Function Description

Complete the maximumSum function in the editor below. It should return a long integer that represents the maximum value of .

maximumSum has the following parameter(s):

• a: an array of long integers, the array to analyze
• m: a long integer, the modulo divisor

Input Format

The first line contains an integer , the number of queries to perform.

The next  pairs of lines are as follows:

• The first line contains two space-separated integers  and (long), the length of  and the modulo divisor.
• The second line contains  space-separated long integers .

Constraints

•  the sum of  over all test cases 

Output Format

For each query, return the maximum value of  as a long integer.

Sample Input

1
5 7
3 3 9 9 5

Sample Output

6

Explanation

The subarrays of array  and their respective sums modulo  are ranked in order of length and sum in the following list:

1.  and 
    and 
   
2. 
   
   
   
3. 
   
   
4. 
   

The maximum value for  for any subarray is .

Maximum Subarray Sum - Hacker Rank Solution

We define  where .

Here,  denotes the sum of all the elements from  to , and  denotes the sum of all the elements from  to .

The Challenge

We must find the maximum value of  for all . The solution to this problem is quite similar to solving the problem of finding the maximum sum in a subarray.

For a particular index , we must find the maximum possible value of  for some .

Let . Now, we want to find the value of  such that  and  is maximized.

Note: 

 is constant for a given , so only  cases are formed.

Case 1: 

Find a  such that  is minimal (which is  when you don't choose any element).

Reason: If , then the difference is positive and is . So we need to find the smallest  (the minimum value when no element is chosen is ).

Remember, we want to maximize  at position .

Case 2: 

Now the minimum value for  is , and the maximum value is .

Reason:  and 

Find , which is strictly .

Reason: The modulo answer will be  where  and  are constant so we just need to find the minimum value of  which is just greater than  to maximize our answer.

Note: For finding the  in the second case, we'll need a balanced binary search tree.

We take the maximum of both the cases and thus find the maximum of the  for all  in time.

Hack

The correct the syntax for using lower_bound in C++ is set_object.lower_bound(value). If you use lower_bound(set_object.begin(), set_object.end(), value), then you'll end up exceeding the time limit.

Problem Setter's code:

C++

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;

void solve()
{
    ll N,M;
    ll x,prefix=0,maxim=0;
    cin>>N>>M;
    set<ll> S;
    S.insert(0);
    for(int i=1;i<=N;i++){
        cin>>x;
        prefix = (prefix + x)%M;
        maxim = max(maxim,prefix);
        set<ll>::iterator  it = S.lower_bound(prefix+1);
        if( it != S.end() ){
            maxim = max(maxim,prefix - (*it) + M );
        }
        S.insert(prefix);
    }
    cout<<maxim<<endl;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)    solve();
    return 0;
}