/*
- 问题：
- 最大子序列问题：给定一整数序列A1，A2，A3...An（可能有负数），求A1~An的一个最大子序列Ai~Aj的和。 */
class Search{
//这段代码哪里有问题？为什么得不到结果？？
double value=0;
double doSearch(int low,int high,int[] arr){
for(int i=low;i<=high;i++){
value+=arr[i];
}
return value;
}
}
public class pptv_bishi {
//，时间复杂度O()。
public static void main(String[] args) {
// TODO Auto-generated method stub
int n;
System.out.println("请输入序列长度n:");
Scanner in=new Scanner(System.in);
n=in.nextInt();
System.out.println("请输入n个序列值:");
int [] arr=new int[n+1];
for(int i=1;i<=n;i++){//输入序列An。
arr[i]=in.nextInt();
}
in.close();
double sum=0;//记录最大子序列和。
double temp=0;
int low=0,high=0;
Search s=new Search();
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
temp=s.doSearch(i,j,arr);
if(temp>sum){
sum=temp;
low=i;
high=j;
}
}
}
System.out.println("the substring is: \nSTART..."+low+"\nEND....."+high+"\nMaxSum is "+sum);
}
}
