题目描述

blablabla

样例

blablabla

算法

(Monotonic Queue) $O(n)$

参考诸位大神的解答，整理代码如下。

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int maxSubarraySum(vector<int>& nums, int m) {
  const int n = nums.size();

  vector<int> preSum(n + 1, 0);
  std::partial_sum(nums.begin(), 
    nums.end(), preSum.begin() + 1);

  int ans = INT_MIN;
  std::deque<int> q({0});

  for (int i = 1; i <= n; i++) {
    while (q.size() && q.front() < i - m) 
      q.pop_front();

    ans = std::max(ans, preSum[i] - preSum[q.front()]);

    while (q.size() && preSum[i] <= preSum[q.back()]) 
      q.pop_back();

    q.push_back(i);
  }

  return ans;
}

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> nums(n, 0);
  for (int i = 0; i < n; ++i)
    cin >> nums[i];

  cout << maxSubarraySum(nums, m);
  return 0;
}