JavaScript：leetcode_53. 最大子序和（貪心，分治）

題目說明

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），傳回其最大和。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。
進階:

如果你已經實作複雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

           

解題思路一

貪心算法。

1. 依次求數組前i項的和，再求和之前，判斷sum的值是否小于0，若小于零，直接抛棄。
2. 若大于0，就sum+=nums[i]
3. 由于子序列是必須要連續的，是以我們需要一個記錄最大值的變量,maxSum.
4. 每次sum求和之後，用maxSum記錄最大值

   maxSum= Math.max(sum, maxSum)

   ;最終傳回max即可

代碼實作一

/**
 * @param {number[]} nums
 * @return {number}
 */
 var maxSubArray = function(nums) {
    let sum = 0;
    let maxSum = Number.MIN_SAFE_INTEGER;
    for (let i = 0; i < nums.length; i++) {
        if (sum < 0) {
            sum = nums[i];
        } else {
            sum += nums[i];
        }
        maxSum = Math.max(maxSum, sum)
    }
    return maxSum
 };
           

解題思路二

分治法。

1. 将nums分為3個部分：
   1. 從nums[mid]處向兩邊求和，取得最大值。
   2. nums的左半邊 （仿照1的方式求得左半邊的和）
   3. nums的右半邊（仿照1的方式求得右半邊的和）
2. 求出這三個和之後，傳回其最大的一個值。
3. 從步驟一得出，我們需用使用遞歸計算。

代碼實作一

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
   
   return fz(0, nums.length-1, nums)
};

function fz(left, right, nums) {
    if (left === right) {
       return nums[left]
    }
    let mid = left + ((right - left) >> 1);
    let leftMax = Number.MIN_SAFE_INTEGER
    let rightMax = Number.MIN_SAFE_INTEGER
    let midMax = crossNum(left, right, nums)
    leftMax = fz(left, mid, nums)
    rightMax = fz(mid+1, right, nums)
    return Math.max(Math.max(midMax, rightMax), leftMax);
}

function crossNum(left, right, nums) {
    if (left === right) {
        return nums[left]
    }
    let mid = left + ((right - left) >> 1)
    let leftSum = 0;
    let leftMax = Number.MIN_SAFE_INTEGER;
    for (let i = mid; i >= left; i--) {
        leftSum += nums[i];
        leftMax = Math.max(leftMax, leftSum)
    }
    let rightSum = 0;
    let rightMax = Number.MIN_SAFE_INTEGER;
    for (let i = mid + 1; i <= right; i++) {
        rightSum += nums[i];
        rightMax = Math.max(rightMax, rightSum)
    }

    return rightMax + leftMax;
}