DP——最大子序和

https://www.acwing.com/problem/content/137/

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

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

输入格式

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

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

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

输出格式

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

数据范围

1≤n,m≤300000

输入样例：

1
2
6 4
1 -3 5 1 -2 3

输出样例：

1
7

解

状态转移方程：集合代表的喊一声所有以i结尾的子段，如果i=3的话，那么集合可能是{1,num[i]}、{1,-3,num[i]}、{1,5,num[i]}、{num[i]} ，目标是求这些集合中的最大值，因为每个集合都有num[i]可先不考虑num[i]。

所以只要考虑f[i-1]+num[i] ,和只有num[i]的集合的最大值。

也就是考虑f[i-1]和0谁最大。

最终的答案是所有集合的值取最大

代码

LeetCode53 不限制最大子序列长度

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxSubArray(int[] num) {
        int last = 0;
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < num.length; i++) {
            int now = Math.max(last, 0) + num[i];
            res = Math.max(res, now);
            last = now;
        }
        return res;
    }
}

acwing 135 限制最大子序列长度

不同的是，对于每一个i，要求前面长度为m这个段内，求一个最小值

可以用一个队列来维护m个数

每次i向后移动，就插入一个数同时队首出列

  • 用一个单调队列
  • 把没用的数删去
  • 变成单调递增的序列
  • 用$0(1)$ 把 min或max找出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public class Main{

    void run(){
        int n = jin.nextInt();
        int m = jin.nextInt();
        nums.add(0);
        for (int i = 0 ; i < n ; i++) nums.add(jin.nextInt());
        for (int i = 1 ; i <= n ; i++) nums.set(i, nums.get(i)+nums.get(i-1));

        int res = Integer.MIN_VALUE;
        for (int i = 1; i <= n ; i++){
            while(!queue.isEmpty() && i - queue.peekFirst() > m) queue.removeFirst();

            if (!queue.isEmpty()) res = Math.max(res, nums.get(i) - nums.get(queue.peekFirst())); // why not peekF -1 ?
            else res = Math.max(res, nums.get(i));                                              // 差点漏掉了
            while(!queue.isEmpty() && nums.get(i) <= nums.get(queue.peekLast())) queue.removeLast();
            queue.offerLast(i);
        }
        res = Math.max(res, nums.get(n) - nums.get(queue.peekFirst()-1));
        System.out.println(res);
    }

    List<Integer> nums = new ArrayList<>();
    Deque<Integer> queue = new LinkedList<>();
    private Scanner jin = new Scanner(System.in);
    public static void main(String[] args) throws Exception {new Main().run();}
}