题解 P3009 【[USACO11JAN]利润Profits】

· · 题解

看到题解区没什么简短的dp代码，处理过程有的地方复杂化了，于是忍不住来一发水文。

这是道线性dp（废话），所以可以边读入边输出。本题也不需要一个a数组，一个f数组，直接合成一个数组凑合着用。

a[i]表示前i个数的最大子段和。

转移方程：a[i] = max(a[i], a[i] + a[i - 1])

由于a[n]不一定是最大值，所以设变量ans随循环更新最大值。

最后注意处理全负数的情况就好了。

总而言之，一个循环丰衣足食。

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

小蒟蒻写得那么认真，就不给个赞吗QwQ 算了，写得那么烂，就不好意思求赞了（还是给一个再走吧）...