 # PROBLEM LINK: Contest Page | CodeChef

Author: Rajan Arora
Tester: Rajan Arora
Editorialist:Rajan Arora

EASY

# PREREQUISITES:

Arrays, Kadane’s Algorithm

# PROBLEM:

Since Valentine’s day is approaching, so Ritik wants to buy roses for his girfriend. He goes to a flower shop to buy roses. There are n roses kept in a line. Each rose has a happiness content related to it. Ritik can only buy continuous sections of the roses or else he wont buy anything. Find the Maximum happiness content that he can buy.

# QUICK EXPLANATION:

Here we need to find the maximum sum subarray which can be found in O(n) using kadane’s algorithm

# EXPLANATION:

Simple idea of the Kadane’s algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far.

# SOLUTIONS:

Setter's Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

int solve(int arr[],int n)
{

``````int c_sum = 0;
int m_sum = INT_MIN;
for(int i=0;i<n;i++)
{

c_sum += arr[i];
if(c_sum > m_sum)
m_sum = c_sum;
if(c_sum < 0)
c_sum = 0;
}

return m_sum;
``````

}

int main()
{
int t;
cin>>t;
while(t–)
{

``````int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];

cout<<solve(arr,n)<<'\n';
``````

}

return 0;

}

Tester's Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

int solve(int arr[],int n)
{

``````int c_sum = 0;
int m_sum = INT_MIN;
for(int i=0;i<n;i++)
{

c_sum += arr[i];
if(c_sum > m_sum)
m_sum = c_sum;
if(c_sum < 0)
c_sum = 0;
}

return m_sum;
``````

}

int main()
{
int t;
cin>>t;
while(t–)
{

``````int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];

cout<<solve(arr,n)<<'\n';
``````

}

return 0;

}

Editorialist's Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

int solve(int arr[],int n)
{

``````int c_sum = 0;
int m_sum = INT_MIN;
for(int i=0;i<n;i++)
{

c_sum += arr[i];
if(c_sum > m_sum)
m_sum = c_sum;
if(c_sum < 0)
c_sum = 0;
}

return m_sum;
``````

}

int main()
{
int t;
cin>>t;
while(t–)
{

``````int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];

cout<<solve(arr,n)<<'\n';
``````

}

return 0;

}