分治法實作求解最大子數組

1. package com.C2;  
2. public class MaxSubArray {  
3.     public static ResultArray find_max_crossing_subarray(SubArray subArray) {  
4.         int[] array = subArray.getArray();  
5.         //先從中間坐标向左進行周遊，順序不能颠倒  
6.         int left_sum = Integer.MIN_VALUE;  
7.         int low = subArray.getMiddle();//這個low是來确定傳回的最大子數組的左邊邊界坐标  
8.         int sum = 0;  
9.         for (int i = low; i >= subArray.getLow(); i--) {  
10.             sum += array[i];  
11.             if (sum > left_sum) {//一旦目前的和變得更大，則取代目前的和并且重置low的值  
12.                 left_sum = sum;  
13.                 low = i;  
14.             }  
15.         }  
16.         //再從中間坐标向左進行周遊  
17.         int right_sum = Integer.MIN_VALUE;  
18.         int high = subArray.getMiddle() + 1;//這個low是來确定傳回的最大子數組的右邊邊界坐标  
19.         sum = 0;  
20.         for (int i = high; i <= subArray.getHigh(); i++) {  
21.             sum += array[i];  
22.             if (sum > right_sum) {//一旦目前的和變得更大，則取代目前的和并且重置high的值  
23.                 right_sum = sum;  
24.                 high = i;  
25.             }  
26.         }  
27.         //傳回最大子數組的下标以及和  
28.         return new ResultArray(low, high, left_sum + right_sum);  
29.     }  
30.     public static ResultArray find_max_subarray(TempArray tempArray) {  
31.         if (tempArray.getLow() == tempArray.getHigh())  
32.             //如果目前問題是左右下标一樣大，則直接傳回，這是問題的基本情況，遞歸的出口，要首先判斷  
33.             return new ResultArray(tempArray.getLow(), tempArray.getHigh(), tempArray.getArray()[tempArray.getLow()]);  
34.         else {  
35.             int middle = (tempArray.getLow() + tempArray.getHigh()) / 2; //計算中間坐标，取  
36.             ResultArray leftResultArray = find_max_subarray(new TempArray(  
37.                     tempArray.getLow(), middle, tempArray.getArray())); //左邊遞歸  
38.             ResultArray rightResultArray = find_max_subarray(new TempArray(  
39.                     middle + 1, tempArray.getHigh(), tempArray.getArray()));    //右邊遞歸  
40.             ResultArray crossingResultArray = find_max_crossing_subarray(new SubArray(  
41.                     tempArray.getLow(), tempArray.getHigh(), middle, tempArray.getArray()));    //跨界的最大數組  
42.             if (leftResultArray.getSum() >= rightResultArray.getSum()  
43.                     && leftResultArray.getSum() >= crossingResultArray.getSum())  
44.                 return leftResultArray;  
45.             else if (rightResultArray.getSum() >= leftResultArray.getSum()  
46.                     && rightResultArray.getSum() >= crossingResultArray.getSum())  
47.                 return rightResultArray;  
48.             else  
49.                 return crossingResultArray;  
50.         }  
51.     }  
52.     static class TempArray {  
53.         int low;  
54.         int high;  
55.         int[] array;  
56.         public TempArray() {  
57.         }  
58.         public TempArray(int low, int high, int[] a) {  
59.             this.setLow(low);  
60.             this.setHigh(high);  
61.             this.setArray(a);  
62.         }  
63.         public int getLow() {  
64.             return low;  
65.         }  
66.         public void setLow(int low) {  
67.             this.low = low;  
68.         }  
69.         public int getHigh() {  
70.             return high;  
71.         }  
72.         public void setHigh(int high) {  
73.             this.high = high;  
74.         }  
75.         public int[] getArray() {  
76.             return array;  
77.         }  
78.         public void setArray(int[] array) {  
79.             this.array = array;  
80.         }  
81.     }  
82.     static class ResultArray {  
83.         int low;  
84.         int high;  
85.         int sum;  
86.         public ResultArray(int low, int high, int sum) {  
87.             this.setLow(low);  
88.             this.setHigh(high);  
89.             this.setSum(sum);  
90.         }  
91.         public ResultArray() {  
92.         }  
93.         public int getLow() {  
94.             return low;  
95.         }  
96.         public void setLow(int low) {  
97.             this.low = low;  
98.         }  
99.         public int getHigh() {  
100.             return high;  
101.         }  
102.         public void setHigh(int high) {  
103.             this.high = high;  
104.         }  
105.         public int getSum() {  
106.             return sum;  
107.         }  
108.         public void setSum(int sum) {  
109.             this.sum = sum;  
110.         }  
111.         @Override  
112.         public String toString() {  
113.             return "ResultArray [low=" + low + ", high=" + high + ", sum="  
114.                     + sum + "]";  
115.         }  
116.     }  
117.     static class SubArray {  
118.         int low;  
119.         int high;  
120.         int middle;  
121.         int[] array;  
122.         public SubArray(int i, int j, int k, int[] a) {  
123.             this.setLow(i);  
124.             this.setHigh(j);  
125.             this.setMiddle(k);  
126.             this.setArray(a);  
127.         }  
128.         public int getLow() {  
129.             return low;  
130.         }  
131.         public void setLow(int low) {  
132.             this.low = low;  
133.         }  
134.         public int getHigh() {  
135.             return high;  
136.         }  
137.         public void setHigh(int high) {  
138.             this.high = high;  
139.         }  
140.         public int getMiddle() {  
141.             return middle;  
142.         }  
143.         public void setMiddle(int middle) {  
144.             this.middle = middle;  
145.         }  
146.         public int[] getArray() {  
147.             return array;  
148.         }  
149.         public void setArray(int[] array) {  
150.             this.array = array;  
151.         }  
152.     }  
153.     public static void main(String[] args) {  
154.         int length = 20000000;  
155.         int[] array = new int[length];  
156.         int max = 500;  
157.         int min = -500;  
158.         for (int i = 0; i < length; i++) {  
159.             array[i] = (int) Math.round(Math.random() * (max - min) + min);//擷取max和min之間的整數  
160.         }  
161.         TempArray t = new TempArray();  
162.         t.setArray(array);  
163.         t.setLow(0);  
164.         t.setHigh(length - 1);  
165.         System.out.println("\r\n"+find_max_subarray(t));  
166.     }  
167. }  

轉載于:https://blog.51cto.com/herculeser/1161314