BCLGSUB - Editorial

editorial
,
1

PROBLEM LINK:

Practice

Author: vaibhav_0318
Tester: zombiedub
Editorialist: vaibhav_0318

DIFFICULTY:

Medium

PREREQUISITES:

Dynamic Programming

PROBLEM:

Choose K disjoint distinct subarrays each of length L from an array of size N such that their sum is maximum.

EXPLANATION:

Let’s choose K subarrays one by one. Suppose we are about to choose some xth subarray and we have best answer for choosing x-1 subarrays from range [0, i] (0 \leq i < N-L) then if we are choosing subarray [i+1, i+L] then answer for it will be sum_of_subarray [i+1,i+2...i+L] + max_answer_for_x-1_till_i.

Thus, the answer for choosing xth subarray can be found in following way:

ans\_for\_xth\_subarray\_till\_i = max(ans\_for\_x-1\_subarray\_till\_i-L + sum\_of\_subarray [i+L+1,i+L+2...i] , ans\_for\_xth\_subarray\_till\_i-1).

So, in the same way, we can build answer from choosing x=1 to x=K.

Also, it is clearly visible that if K*L \geq N-1 then no solution is possible.

TIME COMPLEXITY:

O(N*K)

SOLUTIONS:

Solution 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(v,i) v.begin()+i,v.end()
#define en "\n"
#define mem(a,b) memset(a,b,sizeof(a));
#define F first
#define S second
#define mod 1000000007
#define mod2 998244353

typedef long long int ll;

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int T=1,I;
    cin>>T;
    for(I=1;I<=T;I++){
        ll n,k,l,i,j;
        cin>>n>>k>>l;
        ll a[n+1],pre[n+1];
        pre[0]=0;
        for(i=1;i<=n;i++){
            cin>>a[i];
            pre[i]=pre[i-1]+a[i];
        }
        if(k*l>n){
            cout<<-1<<en;
            continue;
        }
        ll dp[n+1],ans=0;
        mem(dp,0);
        for(i=1;i<=k;i++){
            for(j=n;j>=i*l;j--){
                dp[j]=dp[j-l]+pre[j]-pre[j-l];
                if(i==k){
                    ans=max(ans,dp[j]);
                }
            }
            for(j=i*l+1;j<=n;j++){
                dp[j]=max(dp[j],dp[j-1]);
            }
        }
        cout<<ans<<en;
    }
    return 0;
}