今天晚上尝试用“分而治之”的思想解决求“最大子列和”问题，结果居然成功了，自己都不敢相信自己居然写出了下面的递归代码
  

1. public static int[] getMaxSubsequenceIndex(int[] arr, int start, int end){
   
2.         if(start==end)
   
3.             return new int[]{start,end};
   
4.         int mid=(start+end)/2;
   
5.         return binarySearchMaxSubseq(arr,getMaxSubsequenceIndex(arr,start,mid),getMaxSubsequenceIndex(arr,mid+1,end));
   
6.        }
   

复制代码

下面是全部代码：

1. /*
   
2. 给定K个整数组成的序列{ N1, N2, ..., NK }，“连续子列”被定义为{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= K。
   
3. “最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，
   
4. 其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和,以及和最大的子列高低位角标
   
5. 
   
6. 输入格式：
   
7. 输入第1行给出正整数 K (<= 100000)；第2行给出K个整数，其间以空格分隔。
   
8. 
   
9. 输出格式：
   
10. 在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。
    
11. 
    
12. 输入样例：
    
13. 6
    
14. -2 11 -4 13 -5 -2
    
15. 
    
16. 输出样例：
    
17. 20 1 3
    
18. 
    
19. 
    
20. */
    
21. import java.util.Scanner;
    
22. 
    
23. class  GetMaxSubsequence
    
24. {
    
25.     public static void main(String[] args)
    
26.     {/*
    
27.         Scanner scanner =new Scanner(System.in);
    
28.         System.out.println("请输入一串整数序列，每个整数以空格隔开\n输入样例：-2 11 -4 13 -5 -2");
    
29.         String str=scanner.nextLine();
    
30.         String[] sequence=str.split(" ");
    
31.         int[] arr=new int[sequence.length];
    
32.         for(int i=0;i<arr.length;i++) {
    
33.             arr[i]=new Integer(sequence[i]);
    
34.             //System.out.println(arr[i]);
    
35.         }*/
    
36.         
    
37.         int[] temp={2,7,-8,2,16,-5,-50,-20,-10,-8,-6};
    
38.         System.out.println(getMaxSubsequenceSum(temp));
    
39.         int[] maxIndex=getMaxSubsequenceIndex(temp,0,temp.length-1);
    
40.         System.out.println(maxIndex[0]+"..."+maxIndex[1]);
    
41.         
    
42.     }
    
43. 
    
44. 
    
45. 
    
46. /*该算法的思想是在线处理*/
    
47.     public static int getMaxSubsequenceSum(int[] arr){
    
48.         int ThisSum=0,MaxSum=0,left=0,right=-1,realleft=-1;
    
49.         for(int i=0;i<arr.length;i++){
    
50.             ThisSum+=arr[i];
    
51.             if(ThisSum>MaxSum){
    
52.                 MaxSum=ThisSum;
    
53.                 if(i>=left){
    
54.                     right=i;
    
55.                     realleft=left;
    
56.                 }
    
57.             }
    
58.             else if(ThisSum<0){
    
59.                 ThisSum=0;
    
60.                 left=i+1;
    
61.             }
    
62.         }
    
63.         System.out.println("i:"+realleft+",j:"+right);
    
64.         return MaxSum;
    
65.     }
    
66. 
    
67.        private static int[] binarySearchMaxSubseq(int[] arr,int[] i,int[] j){
    
68.         int sum1=0,sum2=0,sum3=0,max;
    
69.         int[] result=new int[2];
    
70.         for(int k=i[0];k<=i[1];k++)
    
71.             sum1+=arr[k];
    
72.         for(int k=j[0];k<=j[1];k++)
    
73.             sum2+=arr[k];
    
74.         if(sum1>=sum2) max=sum1;
    
75.         else max=sum2;
    
76.         for(int k=i[0];k<=j[1];k++)
    
77.             sum3+=arr[k];
    
78.         if(sum3>max) max=sum3;
    
79. 
    
80.         if(max==sum1){
    
81.             result[0]=i[0];
    
82.             result[1]=i[1];
    
83.         }else if(max==sum2){
    
84.             result[0]=j[0];
    
85.             result[1]=j[1];
    
86.         }else if(max==sum3){
    
87.             result[0]=i[0];
    
88.             result[1]=j[1];
    
89.         }
    
90.         System.out.println("范围："+i[0]+"~"+j[1]+",最大子序列范围："+result[0]+"~"+result[1]);
    
91.         return result;
    
92.     }
    
93. 
    
94.     /*
    
95.     该算法为“分而治之”，即将一个大问题分解成若干小问题
    
96.     */
    
97.     public static int[] getMaxSubsequenceIndex(int[] arr, int start, int end){
    
98.         if(start==end)
    
99.             return new int[]{start,end};
    
100.         int mid=(start+end)/2;
     
101.         return binarySearchMaxSubseq(arr,getMaxSubsequenceIndex(arr,start,mid),getMaxSubsequenceIndex(arr,mid+1,end));
     
102.        }
     
103. }

复制代码

今天晚上尝试用“分而治之”的思想解决求“最大子列和”问题，结果居然成功了，自己都不敢相信自己居然写出了下面的递归代码
  

1. public static int[] getMaxSubsequenceIndex(int[] arr, int start, int end){
   
2.         if(start==end)
   
3.             return new int[]{start,end};
   
4.         int mid=(start+end)/2;
   
5.         return binarySearchMaxSubseq(arr,getMaxSubsequenceIndex(arr,start,mid),getMaxSubsequenceIndex(arr,mid+1,end));
   
6.        }
   

复制代码

下面是全部代码：

1. /*
   
2. 给定K个整数组成的序列{ N1, N2, ..., NK }，“连续子列”被定义为{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= K。
   
3. “最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，
   
4. 其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和,以及和最大的子列高低位角标
   
5. 
   
6. 输入格式：
   
7. 输入第1行给出正整数 K (<= 100000)；第2行给出K个整数，其间以空格分隔。
   
8. 
   
9. 输出格式：
   
10. 在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。
    
11. 
    
12. 输入样例：
    
13. 6
    
14. -2 11 -4 13 -5 -2
    
15. 
    
16. 输出样例：
    
17. 20 1 3
    
18. 
    
19. 
    
20. */
    
21. import java.util.Scanner;
    
22. 
    
23. class  GetMaxSubsequence
    
24. {
    
25.     public static void main(String[] args)
    
26.     {/*
    
27.         Scanner scanner =new Scanner(System.in);
    
28.         System.out.println("请输入一串整数序列，每个整数以空格隔开\n输入样例：-2 11 -4 13 -5 -2");
    
29.         String str=scanner.nextLine();
    
30.         String[] sequence=str.split(" ");
    
31.         int[] arr=new int[sequence.length];
    
32.         for(int i=0;i<arr.length;i++) {
    
33.             arr[i]=new Integer(sequence[i]);
    
34.             //System.out.println(arr[i]);
    
35.         }*/
    
36.         
    
37.         int[] temp={2,7,-8,2,16,-5,-50,-20,-10,-8,-6};
    
38.         System.out.println(getMaxSubsequenceSum(temp));
    
39.         int[] maxIndex=getMaxSubsequenceIndex(temp,0,temp.length-1);
    
40.         System.out.println(maxIndex[0]+"..."+maxIndex[1]);
    
41.         
    
42.     }
    
43. 
    
44. 
    
45. 
    
46. /*该算法的思想是在线处理*/
    
47.     public static int getMaxSubsequenceSum(int[] arr){
    
48.         int ThisSum=0,MaxSum=0,left=0,right=-1,realleft=-1;
    
49.         for(int i=0;i<arr.length;i++){
    
50.             ThisSum+=arr[i];
    
51.             if(ThisSum>MaxSum){
    
52.                 MaxSum=ThisSum;
    
53.                 if(i>=left){
    
54.                     right=i;
    
55.                     realleft=left;
    
56.                 }
    
57.             }
    
58.             else if(ThisSum<0){
    
59.                 ThisSum=0;
    
60.                 left=i+1;
    
61.             }
    
62.         }
    
63.         System.out.println("i:"+realleft+",j:"+right);
    
64.         return MaxSum;
    
65.     }
    
66. 
    
67.        private static int[] binarySearchMaxSubseq(int[] arr,int[] i,int[] j){
    
68.         int sum1=0,sum2=0,sum3=0,max;
    
69.         int[] result=new int[2];
    
70.         for(int k=i[0];k<=i[1];k++)
    
71.             sum1+=arr[k];
    
72.         for(int k=j[0];k<=j[1];k++)
    
73.             sum2+=arr[k];
    
74.         if(sum1>=sum2) max=sum1;
    
75.         else max=sum2;
    
76.         for(int k=i[0];k<=j[1];k++)
    
77.             sum3+=arr[k];
    
78.         if(sum3>max) max=sum3;
    
79. 
    
80.         if(max==sum1){
    
81.             result[0]=i[0];
    
82.             result[1]=i[1];
    
83.         }else if(max==sum2){
    
84.             result[0]=j[0];
    
85.             result[1]=j[1];
    
86.         }else if(max==sum3){
    
87.             result[0]=i[0];
    
88.             result[1]=j[1];
    
89.         }
    
90.         System.out.println("范围："+i[0]+"~"+j[1]+",最大子序列范围："+result[0]+"~"+result[1]);
    
91.         return result;
    
92.     }
    
93. 
    
94.     /*
    
95.     该算法为“分而治之”，即将一个大问题分解成若干小问题
    
96.     */
    
97.     public static int[] getMaxSubsequenceIndex(int[] arr, int start, int end){
    
98.         if(start==end)
    
99.             return new int[]{start,end};
    
100.         int mid=(start+end)/2;
     
101.         return binarySearchMaxSubseq(arr,getMaxSubsequenceIndex(arr,start,mid),getMaxSubsequenceIndex(arr,mid+1,end));
     
102.        }
     
103. }

复制代码