时限：1000ms 内存限制：10000K 总时限：3000ms
描述
给定一整数序列A0，A1， A2，... An-1 （可能有负数），求A0~An-1的一个连续子序列Ai~Aj，使得Ai到Aj的和最大。
输入
先输入一个正整数n(1<n<1000)，再输入n个整数。
输出
输出最大连续子序列的和。
输入样例
10 2 -1 5 -7 2 -1 4 -2 4 -5
输出样例
7
解析：这个题有很多做法，下面介绍两种：
第一种：最简单的暴力枚举，算出所有可能得到的结果，找出最大的，这个算法的时间复杂度是O(N^3)，三层for循环即可：
#include <stdio.h> #include <stdlib.h> int main() { int n,arr[1001]; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&arr[i]); int flag=0; for(int i=0;i<n;i++) { for(int j=i;j<n;j++) { int ans=0; for(int k=i;k<=j;k++) { ans+=arr[k]; } if(ans>flag) flag=ans; } } printf("%d\n",flag); return 0; }
第二种：动态规划。毫无疑问，动态规划是解决这个题最高效的方法，只有O(N)的复杂度。动态规划算法，最重要的是找到一个对的递推公式，我们用dp[n]表示以第n个数结尾的最大连续子序列的和，于是存在以下递推公式：dp[n]=max(dp[n-1],0)+num[n]
，然后在循环过程中记录dp[n]的值，找出最大的即可：
#include <stdio.h>
int main() { int n; int num[1001]; scanf("%d", &n); for(int i=0;i<n; i++) scanf("%d",&num[i]); int ans=num[0];//赋初值，令ans等于第一个数 for(int i=1;i<n;i++) {//对于从第一个开始的每一个数，如果前面的数字大于0，那么这个值变为与前面的和，从第一个开始，如此一来， //num[i]就变为前i个数的最大和 if(num[i-1]>0) num[i]+=num[i-1]; else num[i]+=0; if(num[i]>ans) ans=num[i]; }
printf("%d\n",ans); return 0; }
