【前缀和, 单调队列】最大子序和

题目

135. 最大子序和 - AcWing题库

---

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

注意： 子序列的长度至少是 $1$ 。

输入格式

第一行输入两个整数 $n,m$ 。

第二行输入 $n$ 个数，代表长度为 $n$ 的整数序列。

同一行数之间用空格隔开。

输出格式

输出一个整数，代表该序列的最大子序和。

数据范围

$1 \le n,m \le 300000$

输入样例：

6 4
1 -3 5 1 -2 3

输出样例：

7

解题

方法一：前缀和 单调队列

思路

看到求连续区间之和的问题，首先想到用前缀和进行优化，然后就是枚举区间的问题：暴力枚举所有合法子区间是一种一种方法，但是这种 $O(n^2)$ 的做法在本题的数据范围上肯定会超时；那么不妨尝试一下枚举子区间的右端点。

当以 $i$ 为右端点时，要求的是不超过 $m$ 的连续子序列最大和： $max(s_i - s_{j - 1})$ （$1 \le i - j + 1 \le m$ ^[1]），因为在一次枚举中 $i$ 是固定的，所以 $s_i$ 是一个常量，当 $s_{j-1}$ 取最小时 $s_i - s_{j-1}$ 可以取到最大。于是问题就变成了在以 $i$ 为右端点不超过 $m$ 的连续子序列中求 $s_{j-1}$ 的最小值（滑动窗口求最小值），不难想到使用单调队列进行优化。

注意：枚举 $i$ 是从 $1 \dots n$ ，而 $j-1$ 是可以取到 $0$ 的 ，所以要在单调队列中先加入索引 $0$ 。

参考：AcWing 135. 最大子序和【单调队列优化DP】- 一只野生彩色铅笔

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        int[] s = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            s[i] = s[i - 1] + (int) in.nval; 
        }
        int[] que = new int[n];
        int hh = 0, tt = -1;
        que[++tt] = 0;
        int mx = Integer.MIN_VALUE;
        for (int i = 1; i <= n; ++i) {
            if (hh <= tt && i - que[hh] > m) ++hh;
            mx = Math.max(mx, s[i] - s[que[hh]]);
            while (hh <= tt && s[que[tt]] >= s[i]) --tt;
            que[++tt] = i;
        }
        System.out.println(mx);
    }
}

---

1. $s$ 是由原整数序列 $a$ 构建出的前缀和数组，那么 $sum(a[j \dots i]) = s[i] - s[j - 1]$ ，因为子序列长度不能大于 $m$ ，也就得到了 $1 \le i - j + 1 \le m$ 。 ↩︎