CDVNT01F-Editorial

PROBLEM LINK:

Practice

Contest: CodeVenture 1.0

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 :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile: