题目
Description
The cows have opened a new business, and Farmer John wants to see how well they are doing. The business has been running for N (1 <= N <= 100,000) days, and every day i the cows recorded their net profit P_i (-1,000 <= P_i <= 1,000).
Farmer John wants to find the largest total profit that the cows have made during any consecutive time period. (Note that a consecutive time period can range in length from one day through N days.) Help him by writing a program to calculate the largest sum of consecutive profits.
奶牛们开始了新的生意，它们的主人约翰想知道它们到底能做得多好。这笔生意已经做了N（1≤N≤100,000）天，每天奶牛们都会记录下这一天的利润Pi（-1,000≤Pi≤1,000）。
约翰想要找到奶牛们在连续的时间期间所获得的最大的总利润。（注：连续时间的周期长度范围从第一天到第N天）。
请你写一个计算最大利润的程序来帮助他。
Input
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single integer: P_i
Output
* Line 1: A single integer representing the value of the maximum sum of profits for any consecutive time period.
Sample Input
7 -3 4 9 -2 -5 8 -3
Sample Output
14
思路
当我在洛谷上看到这道水题的算法标签的时候，我一脸懵逼；
竟然是$dp$, 这种题我就从来没用$dp$ 写过；
但是本蒟蒻还是果断放弃了其他写法（线段树等等），开始想 $dp$ 转移方程；
对于本蒟蒻来说，转移方程真的想了好久，还TLE了一次 ;
我们可以设$dp[i]$ 表示以 $i$ 为最后一个取的数，所获的连续的最大利润；
那么对于每一个 $i$ ,加上前面的 $dp[i-1]$ 连续的利润，如果比$a[i]$ 本身还要小，那么$dp[i]$ 就取$a[i]$;
所以转移方程就是
$dp[i]=max(dp[i],dp[i-1]+a[i]);$ $dp[i]$ 需要初始化为 $a[i]$
自认为转移方程有点难想，读者可以自己多模拟几个样例；
代码
#include<bits/stdc++.h> #define re register typedef long long ll; using namespace std; inline ll read() { ll a=0,f=1; char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();} while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();} return a*f; } ll n; ll a[100010],s[100010]; ll dp[100010]; int main() { memset(dp,128,sizeof(dp));//本题最大坑点，利润可以是负数； //128，是memset 里的最小值 n=read(); for(re ll i=1;i<=n;i++) a[i]=read(); for(re ll i=1;i<=n;i++) dp[i]=a[i];//初始化 for(re ll i=1;i<=n;i++) dp[i]=max(dp[i],dp[i-1]+a[i]);//转移方程 ll ans=-1<<30;//ans 不能是 0，因为利润可以是负数 for(re ll i=1;i<=n;i++) ans=max(ans,dp[i]); printf("%lld ",ans); //return 0 噢忘了 }