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;
}