题前吐槽

其实根本用不到 $DP$，只是大材小用罢了，其实这题特别好水过，数据很小。

我回来补发题解了大家见谅哦

题解

一看题目名，“连续部分和”，立刻脑子里面就想到：把所有数加起来就最大呗。

但是再一看数据范围：$-100 \le a_i \le 100$。居然有负数。

这样一来立马想到：把负数踢出去！但是负数不一定是乖乖连续放在首尾的，这样你就被一道红题卡住了。

然后我们转念一想，“连续部分和”，这名字跟“最长连续子序列”好像啊，用 $DP$！

状态好设计，就 $f_i$ 表示前 $i$ 个数最大连续部分和。转移就可以前面的部分和加上自己，或者仅仅自己，取其大者：

$$f_i = max(f_{i-1} + a_i, a_i)$$

最后在统计答案，由于结尾不固定，可以从头到尾遍历，找到最大值。

#include <bits/stdc++.h>
using namespace std;
int n, a[105], f[105], ans;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        f[i] = max(f[i - 1] + a[i], a[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        ans = max(ans, f[i]);
    }
    printf("%d\n", ans);
    return 0;
}

代码这就出来了。

但其实还能再简单，这个递推（$DP$ 以递推形式出现了）只用到了 $f_{i-1}$ 和 $a_i$，完全可以一边输入一边处理。甚至不用存数组，一个 $pref$ 存储 $f_{i-1}$，一个 $x$ 存储 $a_i$。只用了一个循环，防止卡常。

#include <bits/stdc++.h>
using namespace std;
int n, x, pref, f, ans;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &x);
        f = max(pref + x, x);
        pref = f;
        ans = max(ans, f);
    }
    printf("%d\n", ans);
    return 0;
}

非常的精简，不愧是红题。

最后再说一下，这个虽然没了数组，但也是递推。而且从一定意义上讲，也可以是 $DP$。

$AC$ $Code$

#include <bits/stdc++.h>
using namespace std;
int n, x, pref, f, ans;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &x);
        f = max(pref + x, x);
        pref = f;
        ans = max(ans, f);
    }
    printf("%d\n", ans);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, a[105], f[105], ans;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    ans = f[1] = a[1];
    for (int i = 2; i <= n; i++){
        f[i] = max(f[i - 1] + a[i], a[i]);
		ans = max(f[i],ans);//最基础的动态转移方程，以i为结尾的最大最大字段和 //两种转移途径 结尾最大的+第i项 和 第i项 中取最大 ans=max(f[i],ans);
    }
    cout << ans;
    return 0;
} // n 太小了，暴力也过了，纪念发的第一篇题解

就是动态规划呗

和楼上代码除了格式完全一样，防止ky不放出来了

状态转移方程

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

过

前缀和，暴力轻松过了！

#include <bits/stdc++.h>
using namespace std;
int u = -10005,a[105],n,s[105];
int main()
{
    cin >> n;
    for (int i = 1;i <= n;i++)
    {
        cin >> a[i];
        s[i] = a[i] + s[i - 1];
    }
    for (int k = 1;k <= n;k++)
    {
        for (int i = 1;i <= n - k + 1;i++)
        {
            u = max(u,s[i + k - 1] - s[i - 1]);
        }
    }
    cout << u;
    return 0;
}