PROBLEM LINK:
Author: Nikhil Shukla
Tester: Shubham Kushwaha
Editorialist: Nikhil Shukla
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Dynamic Programming, Kadane’s algorithm
PROBLEM:
You are given an array C of n integers where -10^5 <= Ci <= 10^5 and 2 <= n <= 10^5. You have to find two disjoint subarrays A and B from array C such that (A[i] + A[i+1] +….+ A[i+k1]) + (B[j] + B[j+1] +….+ B[j+k2]) should be maximum and k1!=0 and k2!=0 i.e both subrrays should be non-empty and not be overlapping with each other.
QUICK EXPLANATION:
Just apply kadane’s algorithm once from left to right and store the maximum sum subarray value at every index in array prefixdp and do the same thing backwards and store maximum sum subarray at every index in suffixdp. The answer will be max(prefixdp[i]+suffixdp[i+1]) where 1 < i < n or max(prefixdp[i-1] + suffixdp[i]) where 0 < i < n-1.
Time complexity will be O(n) as it will take linear time in both storing and iterating array to find the maximum sum.
EXPLANATION:
As we know we can apply Kadane’s algorithm to find the maximum subarray sum of a given array of size n and in Kadane’s we can observe that it stores maximum sum subarray at every index or of every subarray from index 0 to i where 0 <i<n if we iterate from starting of the array. A naive solution will be to divide the array at every index and apply Kadane’s algorithm in both parts and keep track of the maximum sum value of both parts but it will have O(n^2) time complexity. To optimize this we can use dynamic programming and precalculate the maximum sum at every index from left to right and also from right to left. Now by doing this we can find out the index at which the sum of elements of both subarrays (left and right of the current index) is maximum in O(n).
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll leftdp[100000];
ll rightdp[100000];
int main()
{
ll n;
cin>>n;
vector<ll>g(n);
for(ll i=0;i<n;i++)
cin>>g[i];
ll max_so_far=INT_MIN;
ll max_ending_here=0;
for(ll i=0;i<n;i++)
{
max_ending_here=max_ending_here+g[i];
if(max_so_far<max_ending_here)
{
max_so_far=max_ending_here;
}
if(max_ending_here<0)
max_ending_here=0;
leftdp[i]=max_so_far;
}
max_so_far=INT_MIN;
max_ending_here=0;
for(ll i=n-1;i>=0;i--)
{
max_ending_here=max_ending_here+g[i];
if(max_so_far<max_ending_here)
{
max_so_far=max_ending_here;
}
if(max_ending_here<0)
max_ending_here=0;
rightdp[i]=max_so_far;
}
ll ans=INT_MIN;
for(ll i=0;i<n-1;i++)
{
ans=max(ans,leftdp[i]+rightdp[i+1]);
}
cout<<ans<<endl;
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
#define endl '\n'
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define ai(arr,n) for(int i=0;i<n;i++)cin>>arr[i];
#define ao(arr) for(auto asdfasdfasdf:arr) cout<<asdfasdfasdf<<" ";
#define mi(arr,m,n) for(int i=0;i<m;i++){ for(int j=0;j<n;j++) cin>>arr[i][j];}
#define mo(arr,m,n) for(int i=0;i<m;i++){ for(int j=0;j<n;j++) cout<<arr[i][j]<<" "; cout<<endl;}
#define countsetbits(x) __builtin_popcount(x)
#define ll long long
#define debug cout<<"I AM EXECUTING"<<endl
#define testcases int asdf; cin>>asdf; while(asdf--)
#define vi vector<int>
#define vll vector<long long int>
#define vppo(prs) for(auto x:prs){cout<<x.first<<" "<<x.second<<endl;}
#define For(_,hajmola,adfdf) for(int _ = hajmola; _<adfdf;_++)
string sconvert(ll int n)
{
stringstream ss;
ss<<n;
string str = ss.str();
return str;
}
bool sortbysec(const pair<int,int> &a,
const pair<int,int> &b)
{
return (a.second > b.second);
}
template<typename T>
void imax(T &x,T y){
x = max(x,y);
}
template<typename T>
void imin(T &x,T y){
x = min(x,y);
}
void single()
{
ll int n;
cin>>n;
vector<ll int> arr(n);
ai(arr,n);
vector<ll int> left(n);
vector<ll int> right(n);
ll int sum=0;
ll int current = -1e18;
for(int i=0;i<n;i++){
sum+=arr[i];
imax(sum,0ll);
imax(current,sum);
left[i]=current;
}
sum=0;
current=-1e18;
for(int j=n-1;j>=0;j--){
sum+=arr[j];
imax(sum,0ll);
imax(current,sum);
right[j]=current;
}
cout<<endl;
ll int answer=-1e18;
for(int i=0;i<n-1;i++){
imax(answer,left[i]+right[i+1]);
}
if(answer==0){
sort(rall(arr));
cout<<arr[0]+arr[1]<<endl;
return;
}
cout<<answer<<endl;
return;
}
void multiple()
{
testcases
{
single();
}
}
int main()
{
IOS;
// freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
single();
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll leftdp[100000];
ll rightdp[100000];
int main()
{
ll n;
cin>>n;
vector<ll>g(n);
for(ll i=0;i<n;i++)
cin>>g[i];
ll max_so_far=INT_MIN;
ll max_ending_here=0;
for(ll i=0;i<n;i++)
{
max_ending_here=max_ending_here+g[i];
if(max_so_far<max_ending_here)
{
max_so_far=max_ending_here;
}
if(max_ending_here<0)
max_ending_here=0;
leftdp[i]=max_so_far;
}
max_so_far=INT_MIN;
max_ending_here=0;
for(ll i=n-1;i>=0;i--)
{
max_ending_here=max_ending_here+g[i];
if(max_so_far<max_ending_here)
{
max_so_far=max_ending_here;
}
if(max_ending_here<0)
max_ending_here=0;
rightdp[i]=max_so_far;
}
ll ans=INT_MIN;
for(ll i=0;i<n-1;i++)
{
ans=max(ans,leftdp[i]+rightdp[i+1]);
}
cout<<ans<<endl;
return 0;
}