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();}
}