摘要
Title: 135. 最大子序和
Tag: 前缀和、单调队列
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

135. 最大子序和

• 题意

  输入一个长度为 n 的整数序列，从中找出一段长度不超过 m 的连续子序列，使得子序列中所有数的和最大。
  注意： 子序列的长度至少是 1。

• 思路

  先求前缀和，枚举右端点，求出最小的左端点并做差，更新最大值

  对于最小左端点可以用单调队列进行维护，每次取队头即可

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-02-27 16:35:09
  FilePath: \ACM\Acwing\135.py
  LastEditTime: 2022-02-27 16:46:28
  '''
  
  from collections import deque
  
  N = int(3e5 + 100)
  INF = int(2e9)
  a = [0] * N
  
  if __name__ == "__main__":
      n, m = map(int, input().split())
      a[1:] = list(map(int, input().split()))
      q = deque()
      res = -INF
      for i in range(1, n + 1):
          a[i] += a[i - 1]
      q.append(0)  # 左端点初始值为0
      for i in range(1, n + 1):  #枚举右端点
          while q and i - q[0] > m:
              q.popleft()
          res = max(res, a[i] - a[q[0]]) #下面就是对加入此元素的处理了，所以取最大值要在之前
          while q and a[q[-1]] >= a[i]:
              q.pop()
          q.append(i)
      print(res)