**最大子段和**
很简单的一道Dp题,用$dp[i]$表示$1-i$中的最大子段和
能够得出状态转移方程:$dp[i] = max(dp[i], dp[i]+dp[i-1])$
初始化$dp[i]=num[i]$
代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int n, ans = -20000; 5 int num[200005], dp[200005]; 6 7 int init() { 8 scanf("%d", &n); 9 for(int i = 1; i <= n; i++)scanf("%d", &num[i]), dp[i] = num[i]; 10 return 0; 11 } 12 13 int solve() { 14 for(int i = 2; i <= n; i++) dp[i] = max(dp[i], dp[i-1]+dp[i]); 15 for(int i = 1; i <= n; i++) ans = max(ans, dp[i]); 16 printf("%d", ans); 17 return 0; 18 } 19 20 int main() { 21 init(); 22 solve(); 23 return 0; 24 }最大子段和