每周一算法：连续子序列的和

题目链接

最大子段和

题目描述

给出一个长度为 $n$ 的序列 $a$，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 $n$。

第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个数字 $a_i$。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

7
2 -4 3 -1 2 -4 3

样例输出 #1

4

提示

样例 1 解释

选取 $[3,5]$ 子段 { 3 , ? 1 , 2 } \{3, -1, 2\} {3,?1,2}，其和为 $4$。

数据规模与约定

• 对于 $40\%$ 的数据，保证 $n\le 2\times 10^3$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 2\times 10^5$，$?10^4\le a_i\le 10^4$。

算法思想

求序列中连续且非空的一段，使得这段和最大，求和的最大值可以使用动态规划的思想来处理。

状态表示

$f[i]$表示所有以$i$为右端点的连续子段和的最大值。

最终答案为所有$f[i]$的最大值。

状态计算

从最后一步分析，按照连续子段的长度进行分类：

• 子段长度为$1$，即只包含$1$个数，此时和为$a[i]$
• 子段长度为$2$，包含$2$个数，此时和为$a[i?1]+a[i]$
• 子段长度为$3$，包含$3$个数，此时和为$a[i?2]+a[i?1]+a[i]$
• …
• 子段长度为$i$，包含$i$个数，此时和为$a[1]+a[2]+...+a[i?1]+a[i]$

$f[i]$应取应取以上情况的最大值。

不难看出，从第$2$项开始，每一项都加上了$a[i]$，把$a[i]$提取出来，就变成求 { a [ i ? 1 ] , a [ i ? 2 ] + a [ i ? 1 ] , . . . , a [ 1 ] + a [ 2 ] + . . . + a [ i ? 1 ] } \{a[i-1], a[i-2]+a[i-1],...,a[1]+a[2]+...+a[i-1]\} {a[i?1],a[i?2]+a[i?1],...,a[1]+a[2]+...+a[i?1]}的最大值再加上$a[i]$，即$f[i?1]+a[i]$。因此 f [ i ] = m a x { a [ i ] , f [ i ? 1 ] + a [ i ] } f[i]=max\{a[i],f[i-1]+a[i]\} f[i]=max{a[i],f[i?1]+a[i]}

初始状态

$f[0]$表示前$0$项和的最大值，应尽可能小，由于序列中每一项的范围是$?10^4\le a_i\le 10^4$，存在负数，因此可以让$f[0]=?1e9$。

时间复杂度

• 状态数为$n$
• 状态计算的时间复杂度为$O(1)$，总的时间复杂度为$O(n)$

代码实现

#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int a[N], f[N];
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    //初始状态
    f[0] = -1e9;
    int ans = -1e9;
    //状态计算
    for(int i = 1; i <= n; i ++)
    {
        f[i] = max(a[i], f[i - 1] + a[i]);
        ans = max(ans, f[i]);
    }
    cout << ans;
    return 0;
}

空间优化

根据状态转移方程， f [ i ] = m a x { a [ i ] , f [ i ? 1 ] + a [ i ] } f[i]=max\{a[i],f[i-1]+a[i]\} f[i]=max{a[i],f[i?1]+a[i]}，可以发现$f[i]$只与$f[i?1]$相关，因此不需要用数组存储所有状态，只用一个变量滚动存储即可。

#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    //初始状态
    int f = -1e9, ans = -1e9;
    //状态计算
    for(int i = 1; i <= n; i ++)
    {
        f = max(a[i], f + a[i]);
        ans = max(ans, f);
    }
    cout << ans;
    return 0;
}