TSOH help l

[pie_3]

can anyone help me build logic behind this question.
contest-pop20push21(TSOH)

CodeChef: Practical coding for everyone

[rav1234]

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 .

[pie_3]

ohhh got it thanks bro!!

[vishesh_pandey]

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

[ashish_kaur]

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

[cubefreak777]

I think it should be subarrays instead of subsets

[cubefreak777]

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.

Pop20push21 [TSOH]

Let’s denote M as number of boxes which are inside of some box in optimal solution. Then the answer will be n-M. Let’s mention that we can run binary search to find M. Let’s see how to check if M>=x where x is an integer. We need to determine if we can put x boxes in some other boxes. Obviously we need put boxes with the smallest width inside boxes with the largest width. So, to check if M>=x, we just sort the initial array and check if a[i] *2<=a[n-x+i] for every i in [0;x-1] That is appr…

[vishesh_pandey]

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

[skn1998]

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: CodeChef: Practical coding for everyone

[eraldo_coil]

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