求解hdu1003java题目的动态规划优化方法

这是个什么题呢？我给忘了分类了，哈哈哈哈，好久没动咯。。。。动态规划也行，数字逻辑也行。。。反正就是优化时间，模拟肯定超时。。。

主要想明白两点：

1.从1加到n为负，即sum(1,n)<0,则sum(1,n)&＃43;sum(n,s)

2.从1加到n为正，即sum(1,n>0),则sum(1,n)&＃43;sum(n,s)>sum(n,s);

这就&＃20540;得什么呢？只要是大于0就一直加，其中和最大的肯定是前几项和的最大&＃20540;，不可能是从中间开始的。。

小于0了，就不加了，和清0,重新开始。。

注意：

1.都是负数的情况（max初&＃20540;为-10000，小于-1000）

2.有0的，（多个最大相同&＃20540;，取第一个，即判定时不要等号）

import java.util.Scanner;
public class Main
{

public static void main(String args[])
{

Scanner cin=new Scanner(System.in);
while(cin.hasNext())
{
int n= cin.nextInt();
int i=0;
while(n-->0){
i++;
int s=cin.nextInt();//总个数
int maxStartId=0;//记录最大数的开始id;
int maxEndId=0;//记录最大数的结束位;
int max=-10000;//记录最大值
int sum=0;//记录累加和
int sumStartId=0;//记录累加和开始id;
int sumEndId=0;//记录累加和结束id;

for(sumStartId=sumEndId=1;sumEndId<=s;sumEndId++){
sum+=cin.nextInt();
if(sum>max){//每次更新max记录。。。。要求第一个，所以不要等号。
maxStartId=sumStartId;
maxEndId=sumEndId;
max=sum;
}
if(sum<0){//总和小于0,重新开始。。
sum=0;
sumStartId=sumEndId+1;
}
}

System.out.printf("Case %d:%n%d %d %d%n",i,max,maxStartId,maxEndId);
if(n>0) System.out.println();
}
}
}
}