最大子数组问题

暴力法

是我们很容易就想到的一种解决方法，这种方法就是先从第一个元素遍历到最后一个元素，计算出以第一个元素为起始位置的最大子数组和，然后再以第二个元素开始遍历到最后一个元素，计算出以第二个元素为起始位置的最大子数组和，依次类推，直到计算出以所有元素为起始位置的最大子数组和 代码实现：

Array.prototype.maxSubArray = function () {
    let sum = 0, max_sum = Number.MIN_VALUE
    for (let i = 0; i < this.length; i++) {
        sum = 0
        for (let j = i; j < this.length; j++) {
            sum += this[j]
            if (sum < 0) sum = 0
            max_sum = Math.max(max_sum, sum)
        }
    }
    return max_sum
}
const arr = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
console.log(arr.maxSubArray())

分治法

假设我们需要求解arr[low,high]区间的最大子数组和，那么我么需要将该数组分成两个规模尽量相等的数组，从该数组的中心点即mid = (high - low) / 2分割，左边数组的规模为arr[low, mid]，右边数组的规模为arr[mid+1, high]，然后再求解这两个数组的最大子数组和，但是有一个问题就是如果arr[low,high]区间的最大子数组左区间在arr[low, mid]中，右区间在arr[mid+1,high]中，那么这个时候arr[low,high]区间的最大子数组和就等于max(arr[low, mid]) + max(arr[mid+1,high])，所以arr[low,high]的任意连续的最大子数组arr[i, j]一定会满足下面三个条件之一：

arr[i,j]只出现在arr[low,mid]中
arr[i,j]只出现在arr[mid+1,high]中
跨越了中点:low <= i <= j <= high

判断完边界条件之后我们就可以递归地求解arr[low,mid]和arr[mid+1,high]区间的最大子数组和，即把该区间划分为规模更小的区间，直到被分割的区间有且仅有一个元素时，即该元素就是该区间的最大子数组和，剩下的就是寻找跨越了中点的区间的最大子数组和 计算跨越中点区间的连续最大子数组和：我们只要计算出arr[low,mid]区间的最大子数组和以及arr[mid+1,high]区间的最大子数组和，然后两者相加就行 代码实现：

//计算跨越中间位置的最大子数组
Array.prototype.maxCrossingSubArray = function(mid) {
    let left_sum = right_sum = Number.MIN_VALUE
    let sum = 0
    for(let i = mid; i >= 0; i--) {
        sum += this[i]
        left_sum = Math.max(sum, left_sum)
    }
    sum = 0
    for(let i = mid + 1; i < this.length; i++) {
        sum += this[i]
        right_sum = Math.max(sum, right_sum)
    }
    return left_sum + right_sum
}

递归求解每个子区间的最大子数组和并返回最大值：

Array.prototype.maxSubArray = function() {
    if(this.length < 2) return this[0]
    let mid = Math.floor(this.length / 2)
    return Math.max(this.slice(0, mid).maxSubArray(), this.slice(mid).maxSubArray(), this.maxCrossingSubArray(mid))
}

const arr = [13,-3,-25,20,-3,-16,-23, 18,20,-7,12,-5,-22,15,-4,7]
console.log(arr.maxSubArray())

动态规划解法（kadana算法）

算法思想：遍历数序列的时候，记录以当前元素为结束位置的子序列的最大和，该序列由两部分组成，一部分是以前一个元素为结束位置的子序列的最大和，第二部分是当前元素，即以当前元素为结束位置的子序列的最大和等于max(以前一个元素为结束位置的子序列的最大和，以前一个元素为结束位置的子序列的最大和+当前元素) 当序列中的元素全部都为正数时，那么子序列的最大值就是整个序列的元素相加的和，如果序列中存在负数时，那么就判断以前一个元素为结束位置的子序列的最大和+当前元素的值是否小于0，如果是，那么就把它们的和重新设置为0, 再判断最大值 代码实现：

Array.prototype.maxSubArray = function() {
    let sum = 0, max_sum = Number.MIN_VALUE
    for(let i = 0; i < this.length; i++) {
        sum += this[i]
        if(sum < 0) sum = 0
        max_sum = Math.max(max_sum, sum)
    }
    return max_sum
}
const arr = [13,-3,-25,20,-3,-16,-23, 18,20,-7,12,-5,-22,15,-4,7]
console.log(arr.maxSubArray())

最大子数组问题

暴力法

分治法

动态规划解法（kadana算法）

CATALOG