Directi Online Interview Question :- Two non-overLapping subarrays of size k which gives maximum sum
Directi Online Interview Question.
Two non-overLapping subarrays of size k which gives maximum sum.
This is a 1-D Dp approach ,in O(n) time-complexity.
#include<bits/stdc++.h>
using namespace std;
int pre[1000],a[10000],dp[1000];
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
pre[0]=0;
pre[1]=a[1];
dp[k]=pre[k]; ///upto length k
for(int i=2;i<=n;i++) pre[i]=pre[i-1]+a[i];
for(int i=k+1;i<=n;i++) dp[i]=max(dp[i-1],pre[i]-pre[i-k]);
int ans=0;
for (int i=k;i<=n;i++){
ans = max(ans,dp[i-k]+pre[i]-pre[i-k]);}
cout<<ans<<endl;
return 0;
}
Your code is good for positive numbers but not in general case i.e. for negative no.s also.
ReplyDeleteYour ans should be initialized to some minimum negative integer value n your fourth loop must start from i=2*k.
You can check it by yourself with this testcase
A[]={-2,-1,11,-9,-17,-18}
k=2
@Nidhi , you are right this is not generalized. But the question they asked was only for the positive numbers.
DeleteAnd fourth loop is right, it should start from i=k only.