【NC235948】最大子串和

题目

最大子串和

经典动态规划题 （明明是子数组题目却是子串）

思路

动态规划问题比较难想，但是一般有一种“规律”：

设定一个 $dp$ 数组，其中 $dp[i]$ 表示什么……，则可以得出某个状态转移方程$dp[i]=...dp[i-1]...dp[i+1]$ 之类的

本题算是入门级别的题，按照上面的框架来套，不难得出：

设定一个 $dp$ 数组，其中 $dp[i](i=0,1,...)$ 表示数组前 $i+1$ 个元素能得到的最大和，则可以得出状态转移方程为
$$dp[i]=\{\begin{array}{l}a[0],i=0\\ max(dp[i-1]+a[i],a[i]),i>0\end{array}$$
则最终的答案为 $dp$ 数组的最大值。

为什么状态转移方程是这样写的呢？

因为按照题意，我们对于一个数无非有两种选择：要么将其作为最大子数组的起始位置，要么将其作为上一个子数组的末尾位置。由于要使子数组和最大，所以应该两者选最大值，这就有了状态转移方程。

然后使用 $dp$ 数组还不是最优的解法，我们还可以对其进行优化：

由于 $dp$ 数组只会使用到上一个值（即 $dp[i-1]$ ），所以我们可以使用一个变量来代替 $dp[i-1]$，这就会将 $dp$ 数组优化掉。

代码

// 使用dp数组的代码
#include <stdio.h>
typedef long long LL;

LL max(LL a, LL b) { return a > b ? a : b; }

int main(void) {
    int n = 0;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
    }
    LL ans = a[0], dp[n];
    dp[0] = a[0];
    for (int i = 1; i < n; i++) {
        dp[i] = max(dp[i - 1] + a[i], a[i]);
        ans = max(ans, dp[i]);
    }
    printf("%lld\n", ans);
    return 0;
}

// 优化后的代码，可能一下子很难看懂，可以对照未优化的代码看
#include <stdio.h>
typedef long long LL;

int main(void) {
    int n = 0;
    scanf("%d", &n);
    int a[n], k = 0;
    LL ans = 0LL, t = 0LL;
    for (int i = 0; i < n; i++) {
        scanf("%d", &k);
        t = t > 0 ? t + k : k;
        if (t > ans) ans = t;
    }
    printf("%lld\n", ans);
    return 0;
}