fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. int main() {
  8.  
  9.  
  10.     int n, k;
  11.     cin >> n >> k;
  12.  
  13.     vector < ll > a(n), pmax(n);
  14.  
  15.     for (auto & x: a)
  16.         cin >> x;
  17.  
  18.     pmax[0] = a[0];
  19.  
  20.     for (int i = 1; i < n; i++)
  21.         pmax[i] = max(a[i], a[i] + pmax[i - 1]);
  22.  
  23.     ll sm = 0;
  24.  
  25.     for (int i = 0; i < k; i++)
  26.         sm += a[i];
  27.  
  28.     ll ans = sm;
  29.  
  30.     for (int i = k; i < n; i++) {
  31.         sm += a[i] - a[i - k];
  32.  
  33.         ll cur = sm;
  34.  
  35.         if (pmax[i - k] > 0)
  36.             cur += pmax[i - k];
  37.  
  38.         ans = max(ans, cur);
  39.     }
  40.  
  41.     cout << max(0LL, ans) << endl;
  42.  
  43.     return 0;
  44. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
5 2
1 2 -1 3 -4
stdout
copy 
5
https://ideone.com/cXd45z
Given an array of size “N” , find the subarray whose sum is maximum but at the same time size of that subarray should at-least be “k” (Note - If the answer is negative - print “0”)

-> pmax[i] = maximum subarray sum ending at index “i” and the subarray which is considered should forcefully include the index “i”

-> pmax[i] = max(a[i],a[i]+pmax[i-1])

Intermediate Code Link - https://i...content-available-to-author-only...e.com/gI9yBO

-> kmax[i] = maximum subarray sum ending at index “i” such that size of that subarray>=k


Final Code Link - https://i...content-available-to-author-only...e.com/Lny2Xp
language:
C++ (gcc 8.3)
created:
14 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!