PROBLEM LINK: CodeChef: Practical coding for everyone
Author: Rajan Arora
Tester: Rajan Arora
Editorialist:Rajan Arora
DIFFICULTY:
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;
}