Go-最大子数组问题
最大子数组问题
问题描述: 寻找数组A[1..n]和最大的非空连续子数组。
-
条件: 数组中必须含有负数，不然将毫无意义，因为最大子数组将就是数组A本身。 -
思想：分治思想。 -
a: 完全位于A[low, mid]; 此时 low <= i <= j <= mid -
b: 完全位于A[mid+1, high]中，此时 mid + 1 <= i <= j <= high -
c: 跨越了中点mid， 此时 low <= i <= mid < j < high -
假设我们要求A的子数组A[low, high]的最大子数组。根据分治策略，我们先将A[low,high] 平分 -
那么 A[low,highj]的子数组A[i,j]只有三种可能 -
对于 a 和 b 情况，仍然是最大子数组问题，可递归求解。 -
只需要计算 c 类情况。 -
步骤 -
计算 c 类情况
/*** @title findMaxCrossingSubarray* @description 寻找最大子数组问题中的寻找过中点的最大子数组函数* 总体理念: 对于给定的数组, 其中点坐标mid, 即向左寻找到最大子数组和, 再向右寻找到最大子数组, 返回左右边界及整个数组即可* 空间复杂度: O(n)* 时间复杂度: O(n)* @auth: ncuwen* @param: A 原数组* @param: low 数组起始下标* @param: high 数组末尾下标* @param: mid 数组中点下标, 有 low <= mid <= high* @return: 返回一个下标元组划分跨越中点的最大子数组的边界, 并返回最大子数组中值的和*/func findMaxCrossingSubarray(A []int, low int, mid int, high int) (int, int, int) {leftSum := constants.INT_MINmaxLeft := midsum := 0for i := mid; i >= low; i-- {sum += A[i]if sum > leftSum {leftSum = summaxLeft = i}}rightSum := constants.INT_MINmaxRight := mid + 1sum = 0for j := mid + 1; j <= high; j++ {sum += A[j]if sum > rightSum {rightSum = summaxRight = j}}return maxLeft, maxRight, leftSum + rightSum}
-
求解最大子数组问题的分治算法
/*** @title FindMaxSubarray* @description 寻找最大子数组* 总体理念: 分治思想* 空间复杂度: O(n)* 时间复杂度: O(nlg(n))* @auth: ncuwen* @param: A 原数组* @param: low 数组起始下标* @param: high 数组末尾下标*/func FindMaxSubarray(A []int, low int, high int) (int, int, int){if high == low {return low, high, A[low]} else {mid := (low + high) / 2leftLow, leftHigh, leftSum := FindMaxSubarray(A, low, mid)rightLow, rightHigh, rightSum := FindMaxSubarray(A, mid + 1, high)crossLow, crossHigh, crossSum := findMaxCrossingSubarray(A, low, mid, high)if leftSum >= rightSum && leftSum >= crossSum {return leftLow, leftHigh, leftSum} else {if rightSum >= crossSum {return rightLow, rightHigh, rightSum} else {return crossLow, crossHigh, crossSum}}}}