package Test;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class MaxSubSequenceSum { public static void main(String[] args) throws IOException { // TODO Auto-generated method stub System.out.println("请输入10个数字,以空格隔开"); BufferedReader bufr=new BufferedReader(new InputStreamReader(System.in)); String s=bufr.readLine(); String[] s1=s.split("\\s+"); int[] a=new int[s1.length]; for(int i=0;i<s1.length;i++) { a[i]=Integer.parseInt(s1[i]); } int max=maxSumRec(a,0,a.length-1); System.out.println(max); } /** * 《数据结构与算法分析》书中算法代码实现 * 分治法求子序列最大和，体现递归的优点，时间复杂度O(N*logN) */ private static int maxSumRec(int[] a, int left, int right) { // TODO Auto-generated method stub if(left==right){ return a[left]; } int center=(left+right)/2; int maxLeftSum=maxSumRec(a,left,center); System.out.println("maxLeftSum:"+maxLeftSum); int maxRightSum=maxSumRec(a,center+1,right); System.out.println("maxRightSum:"+maxRightSum); int maxLeftBorderSum=0,leftBorderSum=0; for(int i=center;i>=left;i--){ leftBorderSum +=a[i]; if(leftBorderSum>maxLeftBorderSum) maxLeftBorderSum=leftBorderSum; } int maxRightBorderSum=0,RightBorderSum=0; for(int i=center+1;i<=right;i++){ RightBorderSum +=a[i]; if(RightBorderSum>maxRightBorderSum) maxRightBorderSum=RightBorderSum; } return max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum); } //比较三个值返回最大值 private static int max3(int maxLeftSum, int maxRightSum, int i) { // TODO Auto-generated method stub int temp=0; temp=(maxLeftSum>maxRightSum)?maxLeftSum:maxRightSum; return (temp>i)?temp:i; }}
