1.描述:找出數組A的和最大的非空連續子數組,我們稱這樣的連續子數組為最大子數組。
2. 用分治政策來求解。
a. 假設我們要求A的子數組A[low, high]的最大子數組。根據分治政策,我們先将A[low,high] 平分
b. 那麼 A[low,highj]的子數組A[i,j]隻有三種可能
a)完全位于A[low, mid]; 此時 low <= i <= j <= mid
b) 完全位于A[nid+1, high]中,此時 mid + 1 <= i <= j <= high
c) 跨越了中點mid, 此時 low <= i <= mid < j < high
3. 僞代碼FIND-MAXIMUM-SUBARRAY(A, low, high)
if high == low
return (low, high. A[low]) //隻有一個元素
else
mid = (low + high)/2 //向下取整
(left-low, left-high, left-sum) = FIND-MAXIMUM-SUBARRAY(A, low, mid)
(right-low, right-high, right-sum) = FIND-MAXIMUM-SUBARRAY(A, mid + 1, high)
(cross-low, cross-high, cross-sum) = FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
if left-sum >= right-sum and left-sum >= cross-sum
return (left-low, left-high, left-sum)
else if right-sum >= left-sum and right-sum >= cross-sum
return (right-low, right-high, right-sum)
return (cross-low, cross-high, cross-sum)
FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
left-sum = -∞
sum = 0
for i = mid downto low
sum = sum + A[i]
if sum > left-sum
left-sum = sum
max-left = i
right-sum = -∞
sum =0;
for j = mid + 1 to high
sum = sum + A[j]
if sum > right-sum
right-sum = sum
max-right = j
return (max-left, max-right, left-sum + right-sum)
4. 分析
我之前說過,所有的比較最後都是兩個數比較。把最大子數組通過分治政策最後都是一個元素,這時候就是直接傳回這個數,交給上一層。
這時候數組有兩個數,子數組就到了2所說的比較三種情況,再一層層向上遞交結果
5. 代碼實作
java
public class MaxArray {
private static class Result {
int low;
int high;
int sum;
public Result(int low, int high, int sum) {
this.low = low;
this.high = high;
this.sum = sum;
}
}
static Result findMaximumSubarray(int[] A, int low, int high) {
if (low == high) {
return new Result(low, high, A[low]);
} else {
int mid = (low + high)/2;
Result leftResult = findMaximumSubarray(A, low, mid);
Result rightResult = findMaximumSubarray(A, mid+1, high);
Result crossResult = findMaxCrossingSubarray(A, low, mid, high);
if (leftResult.sum >= rightResult.sum && leftResult.sum >= crossResult.sum)
return leftResult;
else if (rightResult.sum >= leftResult.sum && rightResult.sum >= crossResult.sum)
return rightResult;
else return crossResult;
}
}
static Result findMaxCrossingSubarray(int[] A, int low, int mid, int high) {
//向左試探
int leftSum = Integer.MIN_VALUE; //哨兵
int maxLeft = mid;
int sum = 0;
for (int i = mid; i >= low; i--) {
sum += A[i];
if (sum > leftSum) {
leftSum = sum;
maxLeft = i;
}
}
//向右試探
int rightSum = Integer.MIN_VALUE;
int maxRight = mid + 1;
sum = 0;
for (int j = mid + 1; j <= high; j++) {
sum += A[j];
if (sum > rightSum) {
rightSum = sum;
maxRight = j;
}
}
//将兩邊的結果合起來
return new Result(maxLeft, maxRight, leftSum + rightSum);
}
public static void main(String[] args) {
int[] A = {-1, 5, 6, 9, 10, -9, -8, 100, -200};
Result result = findMaximumSubarray(A, 0, A.length-1);
System.out.println(result.low + "," + result.high + " " + result.sum);
}
}
python
def find_maximum_subarray(nums, low, high):
if low == high:
return {"low": low, "high": high, "sum": nums[low]}
else:
mid = int((low + high) / 2)
left_result = find_maximum_subarray(nums, low, mid)
right_result = find_maximum_subarray(nums, mid + 1, high)
cross_result = find_max_crossing_subarray(nums, low, mid, high)
if left_result["sum"] >= right_result["sum"] and left_result["sum"] >= cross_result["sum"]:
return left_result
else:
if right_result["sum"] >= left_result["sum"] and right_result["sum"] >= cross_result["sum"]:
return right_result
else:
return cross_result
def find_max_crossing_subarray(nums, low, mid, high):
left_sum = -float('inf')
total = 0
max_left = mid
for i in range(mid, low-1, -1):
total += nums[i]
if total > left_sum:
left_sum = total
max_left = i
rigth_sum = -float('inf')
total = 0
max_right = mid + 1
for j in range(mid+1, high+1):
total += nums[j]
if total > rigth_sum:
rigth_sum = total
max_right = j
return {"low": max_left, "high": max_right, "sum": left_sum + rigth_sum}
if __name__ == "__main__":
numss = [-1, 5, 6, 9, 10, -9, -8, 100, -200]
result = find_maximum_subarray(numss, 0, len(numss)-1)
print(result)
再分享個python用切片的方法
def find_maximum_subarray_slice(nums):
max_sum = -float('inf')
result = {}
for i in range(len(nums)+1):
for j in range(i, len(nums)+1):
total = sum(nums[i:j])
if total > max_sum:
max_sum = total
result["low"] = i
result["high"] = j-1
result["sum"] = max_sum
return result
C語言
typedef struct{
int low;
int high;
int sum;
}result;
result find_maximum_subarray(int [], int, int);
result find_max_crossing_subarray(int [], int, int, int);
int main()
{
int arr[] = {-1, 5, 6, 9, 10, -9, -8, 100, -200};
result re = find_maximum_subarray(arr, 0, 8);
printf("%d, %d, %d\n", re.low, re.high, re.sum);
return 0;
}
result find_maximum_subarray(int arr[], int low, int high)
{
if (low == high)
{
result re;
re.low = low;
re.high = high;
re.sum = arr[low];
return re;
}
else
{
int mid = (low + high) / 2;
result left_result = find_maximum_subarray(arr, low, mid);
result right_result = find_maximum_subarray(arr, mid + 1, high);
result cross_result = find_max_crossing_subarray(arr, low, mid, high);
if(left_result.sum >= right_result.sum && left_result.sum >= cross_result.sum)
return left_result;
else if(right_result.sum >= left_result.sum && right_result.sum >= cross_result.sum)
return right_result;
else return cross_result;
}
}
result find_max_crossing_subarray(int arr[], int low, int mid, int high)
{
int left_sum = -((unsigned)(~0) >> 1); //設定哨兵
int sum = 0;
int i, max_left;
for(i = mid; i >= low; i--)
{
sum += arr[i];
if(sum > left_sum)
{
left_sum = sum;
max_left = i;
}
}
int right_sum = -((unsigned)(~0) >> 1);
sum = 0;
int j, max_right;
for(j = mid+1; j <= high; j++)
{
sum += arr[j];
if(sum > right_sum)
{
right_sum = sum;
max_right = j;
}
}
result re;
re.low = max_left;
re.high = max_right;
re.sum = left_sum + right_sum;
return re;
}