fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. long long maxSubarraySumAtLeastK(const vector<long long>& a, int k) {
  8.     int n = a.size();
  9.     if (n < k) return 0; 
  10.  
  11.     // pmax[i] = maximum subarray sum ending at index "i"
  12.     vector<long long> pmax(n);
  13.     pmax[0] = a[0];
  14.     for (int i = 1; i < n; i++) {
  15.         pmax[i] = max(a[i], a[i] + pmax[i - 1]);
  16.     }
  17.  
  18.     // kmax[i] = maximum subarray sum ending at index "i" such that size >= k
  19.     vector<long long> kmax(n, 0); 
  20.  
  21.     // 1. Calculate the sum of the first window of size 'k'
  22.     long long current_window_sum = 0;
  23.     for (int i = 0; i < k; i++) {
  24.         current_window_sum += a[i];
  25.     }
  26.  
  27.     // Base case: The first valid subarray of at least size k ends at index k-1
  28.     kmax[k - 1] = current_window_sum;
  29.  
  30.     // 2. Populate the rest of the kmax array using the max() function
  31.     for (int i = k; i < n; i++) {
  32.         // Shift the window of size 'k' by 1 step
  33.         current_window_sum = current_window_sum + a[i] - a[i - k];
  34.  
  35.         // Compare taking only the current window vs. taking the current window + best prefix
  36.         kmax[i] = max(current_window_sum, current_window_sum + pmax[i - k]);
  37.     }
  38.  
  39.     // 3. The answer is the maximum value in our kmax array
  40.     long long overall_max = kmax[k - 1];
  41.     for (int i = k; i < n; i++) {
  42.         overall_max = max(overall_max, kmax[i]);
  43.     }
  44.  
  45.     // Return 0 if the answer is negative
  46.     return max(0LL, overall_max);
  47. }
  48.  
  49. int main() {
  50.     // Fast I/O for Competitive Programming
  51.     ios_base::sync_with_stdio(false);
  52.     cin.tie(NULL);
  53.  
  54.     int t = 1;
  55.     // cin >> t; // Uncomment if there are multiple test cases
  56.  
  57.     while (t--) {
  58.         int n, k;
  59.         if (!(cin >> n >> k)) break;
  60.  
  61.         vector<long long> a(n);
  62.         for (int i = 0; i < n; i++) {
  63.             cin >> a[i];
  64.         }
  65.  
  66.         cout << maxSubarraySumAtLeastK(a, k) << "\n";
  67.     }
  68.  
  69.     return 0;
  70. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
5 2
1 2 -1 3 -4
stdout
copy 
5
https://ideone.com/xDMlTP
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:
20 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!