MAX_DRINKS -Editorial

Practice

Author: Kunal Demla

EASY

Arrays

PROBLEM:

Given an Array Arr return the maximum sum of all sub-arrays.

QUICK EXPLANATION:

Traverse the array, checking for the current sum up till now, and output the max it reaches, while setting it to 0, if it goes negative.

EXPLANATION:

Take 2 variables currsum, maxsum. The currsum stores the sum at current time while traversing the array. maxsum stores the maximum value of current sum obtained while traversing the whole array.
Since we need the maximum sum, it is obvious we donâ€™t want our subarray to have any subarrays on extremes with a negative sum, hence whenever currsum drops below 0, we decide to ignore the previous sub- array and set currsum back to 0. Therefore, for any i, the currsum will indicate a non-negative sum while include the i th element to the sub-array.
Output the maxsum after the traversal of array is complete.

SOLUTIONS:

Setter's Solution
``````#include<bits/stdc++.h>
using namespace std;
#define ll long long int

void solve()
{
ll n,x,y,i,j;
cin>>n;
int a[n];
for(i=0;i<n;i++)
cin>>a[i];
ll cursum=0,maxsum=0;
for(i=0;i<n;i++)
{
cursum+=a[i];
if(cursum<0)
cursum=0;
if(cursum>maxsum)
maxsum=cursum;
}
cout<<maxsum;
}

int main()
{
int t=1;
cin>>t;
while(t--)
{
solve();
cout<<"\n";
}
return 0;
}
``````
Tester's Solution
``````import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t;
t=sc.nextInt();
while(t-->0)
{
int n;
n=sc.nextInt();
int a[]=new int[n];
int i;
int currsum=0,maxsum=0;
for(i=0;i<n;i++)
{
a[i]=sc.nextInt();
currsum+=a[i];
if(currsum<0)
currsum=0;
if(currsum>maxsum)
maxsum=currsum;
}
System.out.println(maxsum);
}
}
}
``````