Posts

Showing posts from May, 2016

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