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