最大子序列问题：给定一整数序列A1，A2，A3...An（可能有负数），求A1~An的一个最大子序列Ai~Aj的和。

这是一道PPTV2015年校园招聘笔试题目。

例：一次程序运行结果

请输入序列长度n:
6
请输入n个序列值:
-1 3 -2 4 5 -6
the substring is: 
START...2
END.....5
MaxSum is 10.0

/*
 * 问题：
 * 最大子序列问题：给定一整数序列A1，A2，A3...An（可能有负数），求A1~An的一个最大子序列Ai~Aj的和。
 * 
 */


import java.util.Scanner;
public class pptv_bishi {
//双重循环法求解，时间复杂度O(n*3)。
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;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
temp=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);


}


private static double doSearch(int low,int high,int[] arr) {
// TODO Auto-generated method stub
double value=0;

for(int i=low;i<=high;i++){
value+=arr[i];
}
return value;


}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！