PROBLEM LINK:
Setter: Jaydeep Mulani
Tester: Malhar Patel
Editorialist: Nisarg Thakkar
DIFFICULTY:
Simple
PREREQUISITES:
Basic observations, Kadane’s Algorithm
PROBLEM:
The idea behind the problem boils down to following : You are given an array of size N and you need to find the maximun sum subarray.
( A subbarray is a contiguous part of array. An array that is inside another array.)
EXPLANATION
Let’s take a 0-indexed array:
arr: [5, 7, -3, 2, 9, 6, 16, 22, 21, 29, -14, 10, 12]
We can start the subarray at any point.
Let’s say we start at index 2 i.e., arr[2] = -3. Now, at index 3, the sum will be -3 + 2 = -1. If we started the subarray at index 3 instead, the sum at index 3 is 2, which is greater than the previous sum.
So we have two choices: either start at the current index or add the current element to the previous sum.
And since we want the maximum subarray sum, we add the current element to the maximum of 0 and previous sum (zero here denotes that we’re starting anew from the current element).
TIME COMPLEXITY
Time complexity is O(T*N).
SOLUTIONS:
CPP Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define llu unsigned long long int
#define fo(i,n) for(int i=0;i<n;i++)
#define eb emplace_back
#define M 1000000007
#define vi vector
#define vlli vector
#define pi pair<int,int>
#define mp make_pair
#define mapi map<int,int>
ll max(ll x,ll y)
{
if(x>y)
return x;
return y;
}
ll min(ll x,ll y)
{
if(x<y)
return x;
return y;
}
void yes()
{
cout << “YES” << endl;
}
void no()
{
cout << “NO” << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//cin.ignore(numeric_limits::max(),‘\n’);
//const unsigned int M=1000000007;
ll test;
cin >> test;
//test=1;
while(test–)
{
ll n;
cin>>n;
ll a[n];
fo(i,n) cin>>a[i];
ll maxsum=INT_MIN,sum=0,maxlen=-1,s=0,e=-1;
fo(i,n)
{
sum+=a[i];
if(maxsum<=sum) maxsum=sum, e=i, maxlen=(maxlen,e-s+1);
if(sum<0) sum=0, s=i+1;
}
cout << maxlen << endl;
}
return 0;
}
Feel free to Share your approach, if you want to. (even if its same 
) . Suggestions are welcomed as always had been. 