[USACO11JAN] Profits S

题意

给出连续 N 天的利润 P_i，利润可能为正也可能为负。

要求在所有连续时间段中，找到一个总利润最大的区间，并输出它的利润和。

思路

最直接的做法是枚举所有连续区间，然后计算区间和。

先看一个可以直接验证想法的朴素解：

cpp

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
30
31
32#include <bits/stdc++.h>
using namespace std;

// brute.cpp：枚举所有连续区间，直接求区间和。

const int MAXN = 100005;

int n;
long long a[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    long long ans = a[1];

    for (int l = 1; l <= n; l++) {
        long long sum = 0;
        for (int r = l; r <= n; r++) {
            sum += a[r];
            ans = max(ans, sum);
        }
    }

    cout << ans << '\n';
    return 0;
}

这份暴力代码枚举左端点和右端点，复杂度是 $O(n^2)$ ， $n = 10^5$ 时肯定过不了。

关键观察是：如果我们只关心“必须以第 i 天结尾”的最优区间，那么它只有两种情况：

直接从第 i 天自己开一段；
把“以第 i-1 天结尾”的最优区间接上今天。

于是设：

dp[i] = 以第 i 天结尾的最大连续利润

转移式就是：

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

这个式子很好理解：

如果 dp[i-1] 是负贡献，那就不要前面那段，直接从 a[i] 重新开始；
如果 dp[i-1] 是正贡献，就把它接上。

最后答案不是某个固定的 dp[i]，而是所有 dp[i] 中的最大值。

`i`	`a[i]`	`dp[i]`
1	`-3`	`-3`
2	`4`	`4`
3	`9`	`13`
4	`-2`	`11`
5	`-5`	`6`
6	`8`	`14`
7	`-3`	`11`

从表里可以看到，最大值出现在 $i = 6$ ，也就是区间 [2,6]，答案为 14。

DP 公式

设 $dp_i$ 表示以第 $i$ 天结尾的最大连续利润。初始化：

dp_1=a_1

转移为：

dp_i=\max(a_i,\ dp_{i-1}+a_i)

最终答案是所有结尾位置的最大值：

\max_{1\leqslant i\leqslant n} dp_i

公式解释：连续子段如果以第 i 天结尾，要么只取当天利润，要么接在前一天结尾的最佳子段后面。若前面的贡献为负，就重新开始更好；若为正，就接上更好。

代码

cpp

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
30#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
long long a[MAXN];
long long dp[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    dp[1] = a[1];
    long long ans = dp[1];

    for (int i = 2; i <= n; i++) {
        // dp[i] 表示“必须以第 i 天结尾”的最大连续利润。
        dp[i] = max(a[i], dp[i - 1] + a[i]);
        ans = max(ans, dp[i]);
    }

    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n)$
空间复杂度： $O(n)$

总结

这题是最大连续子段和的标准模型。

一旦把问题改写成“以 i 结尾的最优值”，就能把原本的区间枚举压成线性递推。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

DP 公式

代码

复杂度

总结

一图流解析