侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-02-27 / 0 评论 / 0 点赞 / 451 阅读 / 810 字
温馨提示:
本文最后更新于 2023-02-27,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

135. 最大子序和 - AcWing题库


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

注意: 子序列的长度至少是 11

输入格式

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

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

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

输出格式

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

数据范围

1n,m3000001 \le n,m \le 300000

输入样例:

6 4
1 -3 5 1 -2 3

输出样例:

7

解题

方法一:前缀和 单调队列

思路

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

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

注意:枚举 ii 是从 1n1 \dots n ,而 j1j-1 是可以取到 00 的 ,所以要在单调队列中先加入索引 00

参考: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. ss 是由原整数序列 aa 构建出的前缀和数组,那么 sum(a[ji])=s[i]s[j1]sum(a[j \dots i]) = s[i] - s[j - 1] ,因为子序列长度不能大于 mm ,也就得到了 1ij+1m1 \le i - j + 1 \le m↩︎

0

评论区