时间复杂度Ｏ(n)
序列：-2 11 -4 13 -5 -2
//最大连续子序列和//使用到状态转移方程#include <cstdio>#include "algorithm"using namespace std;const int maxn =10010;int A[maxn],dp[maxn];//A存放数字序列 dp存放以A[i]结尾的连续序列最大和int main() { int n; scanf("%dd",&n); for(int i=0;i<n;i++) { scanf("%d",&A[i]); } //边界 dp[0]=A[0]; for(int i=1;i<n;i++) { //状态转移方程 dp[i]=max(A[i],dp[i-1]+A[i]); } //寻找以A[i]结尾的最大序列和 int k=0; for (int i=0;i<n;i++) { if(dp[i]>dp[k]) k=i; } for(int i=0;i<n;i++) printf("%d ",dp[i]); printf("n"); printf("%d %dn",k,dp[k]); return 0;}/*6 -2 11 -4 13 -5 -2 */
测试结果：