无限制最长连续的子序列和

题目链接

动态规划转移方程

1
dp[i] = max(dp[i-1] + a[i], a[i]);

最终结果在 dp 数组中线性扫描找出最大值：

1
2
int pos = max_element(dp + 1, dp + 1 + n) - dp;
cout << dp[pos] << " ";

dp[i] 表示以序列中第 i 个数字结尾的最大子段和。
转移方程分析：

  • 如果选择第 i-1 个数，则由 dp[i-1] 转移而来。
  • 如果不选择第 i-1 个数，则只能自己作为一个子段存在，因为必须以第 i 个数结尾。

优化：记录子段端点

在题目中，还需要给出具体是哪段子段和最大（即左端点和右端点）。
初始方法：先求出最大值，再排序所有符合最大值的子段，按题目要求取左端和右端尽可能小的子段。
优化方法：在线性扫描时维护最大值，同时更新左右端点。

有长度限制最长连续的子序列和

类型：单调队列优化 DP

题目描述

给定一个长度为 n 的序列 a，找出其中元素总和最大且长度不超过 m 的连续子区间。

闫氏DP分析法

  • 状态表示：f_i 表示以 i 为右端点，长度不超过 m 的连续子区间。
  • 属性：f_i 表示区间的总和最大（Max）。
  • 状态转移方程：

    fi=max⁡{si−sj}(1≤i−j≤m)f_i = \max\{s_i - s_j\} \quad (1 \le i - j \le m)

    其中，s_i 为前缀和，j 的范围为 i - m <= j <= i - 1。
    进一步优化：

    fi=si−min⁡{sj}(1≤i−j≤m)f_i = s_i - \min\{s_j\} \quad (1 \le i - j \le m)

单调队列优化

从前向后维护一个长度不超过 m 的区间的最小值，使用单调队列优化。
时间复杂度：O(n)（每个元素至多入队出队一次，每次转移为 O(1)）。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;

int n, m;
LL s[N], que[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &s[i]), s[i] += s[i - 1];  // 处理前缀和

    LL res = -1e18;
    int hh = 0, tt = 0; que[0] = 0;
    for (int i = 1; i <= n; i++) {
        while (hh <= tt && i - que[hh] > m) hh++;  // 维护窗口大小
        res = max(res, s[i] - s[que[hh]]);         // 更新最大值
        while (hh <= tt && s[que[tt]] >= s[i]) tt--;  // 维护单调队列
        que[++tt] = i;
    }
    printf("%lld\n", res);
    return 0;
}

参考链接：
单调队列优化DP题解