这是一道简单的DP（dynamic programing）问题。计算最大子序列。
在解题时需要注意考虑完全，还有就是算法的完整程度。
可以用这两个去测试完整度：-1，-2，-3，-4，-5；0，0，0，0，0
在计算中需要使用到动态规划的状态以及状态转移方程。
在这题中，状态是子序列的和，状态转移方程是，某个数与以某个数结尾的子序列中的最大子序列的大小比较
1 for(i = 1;i < n;i++){ 2 if(num[i] > d[i - 1] + num[i]){//如果num[i]大于num[i] + d[i - 1](状态)，那就不用考虑状态，直接进行状态转移 3 endex[i] = index[i] = i + 1; 4 d[i] = num[i]; 5 } 6 else{//反之，继续累计 7 endex[i] = i + 1; 8 index[i] = index[i - 1]; 9 d[i] = d[i - 1] + num[i]; 10 } 11 }
贴上AC代码：
#include<stdio.h>
#include<stdlib.h>
int main(){
int i = 0;
int n = 0;
int r = 0;
int max;
int maxi = 0;
int maxe = 0;
int casen = 0;
int *num;
int *d,*index,*endex;
scanf("%d",&casen);
while(casen --)
{
if(r) printf("\n");
scanf("%d",&n);
num = (int *)malloc(sizeof(int) * n);//动态开辟内存，避免空间不足
d = (int *)malloc(sizeof(int) * n);
index = (int *)malloc(sizeof(int) * n);
endex = (int *)malloc(sizeof(int) * n);
for(i = 0 ;i < n;i ++){
scanf("%d",&num[i]);
}
index[0] = 1;
endex[0] = 1;
d[0] = num[0];
for(i = 1;i < n;i++){
if(num[i] > d[i - 1] + num[i]){
endex[i] = index[i] = i + 1;
d[i] = num[i];
}
else{
endex[i] = i + 1;
index[i] = index[i - 1];
d[i] = d[i - 1] + num[i];
}
}
max = d[0];
maxi = 1;
maxe = 1;
for(i = 1;i < n;i ++){
if(max < d[i]){
max = d[i];
maxi = index[i];
maxe = endex[i];
}
}
r ++;
printf("Case %d:\n",r);
printf("%d %d %d\n",max,maxi,maxe);
}
return 0;
}
原文：http://www.cnblogs.com/zhuhongjongy/p/4948594.html