TSOH help l

can anyone help me build logic behind this question.
contest-pop20push21(TSOH)
https://www.codechef.com/POPU2021/problems/TSOH

If we consider every index i ,then one subarray would be lying on the left of i and the other on the right. So our task is to find for every index i the maximum sum subarray on the left of it and max sum sub array on right of it .Then take max(left[i]+right[i]) for all i .

2 Likes

ohhh got it thanks bro!!

I am still confused with this question. Please can anyone explain it more …I am new to codechef

You are given an array. You need to divide the array into two disjoint subarrays such that their sum is maximum possible. Atlast print the sum of Subset1+Subset2

1 Like

I think it should be subarrays instead of subsets

2 Likes

Just apply kadanes algorithm on the sorted and reverse sorted array and then obtain the prefix maximums for both of them. Then iterate over all indices and find max answer for each index by adding the contributions from the left and right half. Check the code for details it’s quite readable.

AC_CODE
#include<bits/stdc++.h>
using namespace std ;
signed main(){
  int n,mx=0 ;
  cin >> n ;
  vector<int>a(n),l(n),r(n);
  for(int &x:a)
    cin >> x ;
  int ans=a[0]+a[n-1] ;
  for(int i=0;i<n;i++)
    mx = max(a[i],mx+a[i]),l[i]=mx ; mx=0;
  for(int i=n-1;~i;--i)
    mx = max(a[i],mx+a[i]),r[i]=mx ;  
  for(int i=1,j=n-2;i<n;i++,j--)
    l[i]=max(l[i-1],l[i]),r[j]=max(r[j],r[j+1])  ;
  for(int i=1;i<n-1;i++)
    ans = max(ans,l[i-1]+r[i+1]) ;
  cout << ans ;
}

I got to know this approach from the following thread.

1 Like

hey … We can’t apply Kadanes algorithm here as kadanes algorithm would not work if there will be only negative numbers. Right ?

No, it will still work and pick things optimally.
Let’s use Kadane’s on only -ve number array and see:
let the arr be : -10 -1 -30 -40 -3 -11
forward : -10 -1 -30 -40 -3 -11
backward : -10 -1 -30 -40 -3 -11
forward_max : -10 -1 -1 -1 -1 -1
backward_max: -1 -1 -3 -3 -3 -11

Clearly here it will provide the answer as -4 in this case.
Check my AC Code once: Solution: 41608006 | CodeChef

thanks, you explained the intuition and though process really well!