基本按照書上的流程實作了遞歸解決最大子數組問題,複雜度為O(nlgn)
package 最大子數組4_1;
public class Solution {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = new int[] {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4};
int[] result = new int[3];
System.out.println(findMaxSubArray(arr, 0, arr.length-1)[2]);
}
static int[] findCrossMax(int[] arr, int low,int mid,int high) {
if(low == high) {
return new int[] {low,high,arr[low]};
}
int leftIndex = mid,rightIndex = mid +1;
int sum = 0;
int leftSum = Integer.MIN_VALUE, rightSum = Integer.MIN_VALUE;
for(int i = mid;i>=low;i--) {
sum = sum + arr[i];
if(sum > leftSum) {
leftSum = sum;
leftIndex = i;
}
}
sum = 0;
for(int i = mid+1;i <= high; i++) {
sum = sum + arr[i];
if(sum > rightSum) {
rightSum = sum;
rightIndex = i;
}
}
return new int[] {leftIndex,rightIndex,leftSum + rightSum};
}
static int[] findMaxSubArray(int[] arr, int low,int high) {
if(low == high) {
return new int[]{low,high,arr[low]};
}
int mid = (low + high) /2;
int[] resultLeft,resultRight,resultCross = new int[3];
resultLeft = findMaxSubArray(arr, low, mid);
resultRight = findMaxSubArray(arr, mid+1, high);
resultCross = findCrossMax(arr, low, mid, high);
if(resultLeft[2] > resultCross[2] && resultLeft[2] > resultRight[2]) {
return resultLeft;
}
else
return resultCross[2] > resultRight[2]? resultCross:resultRight;
}
}