53. Maximum Subarray

题目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

传入一 数字阵列 nums，阵列中的数字 有正数有负数，找出子序列中，加总最多的序列

e.g. 序列 [-2,1,-3,4,-1,2,1,-5,4]

加总答案是 4 - 1 + 2 + 1 = 6

Example

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Input: nums = [1]
Output: 1

Input: nums = [5,4,-1,7,8]
Output: 23

演算法

1. 选择起始点，当作目前加总最多的数字

有数字的话一定要回传加总数字，如果阵列都是负数的话，也要想办法找出负数最小的数是哪一个

所以所有负数都是单独计算，直到有找到 加总起来是正数，就会以那个正数当起点计算

• 正数不管再怎麽选也比负数大

EX1. 整数序列 [-1]

加总答案是 - 1

EX2. 整数序列 [-3, -1]

加总答案是 - 1

EX3. 整数序列 [-3, -1, 1]

加总答案是 1

2. 当遇到第一个正整数，表示至少整体加总的最大数字一定是正整数（只选一个）

当遇到第一个正整数，会将加总最多的序列设定为目前数字，且确定加总数字一定会是正数，至少是自己本身一个正数

所以当后方的数字，与前面的数字做加总，只要小于 0就一定不是要找的序列，因为加总后，后面的负数会完全抵消前面的正数，所以要重新计算新的序列

EX1. 整数序列 [-1, 3, -1, 1, -4]

正数 3 后面的加总，无法超过 3 本身 甚至会变成负的 3 - 1 + 1 -4 = -1

当加总 小于 0 表示这一整个序列中间都是做白工，完全没办法让原本序列变大，所以当发现这样的序列，导致加总会变成 负数，那就可以直接跳过不用检查，除非这个序列的加总可以超过 原本正数 3 本身

EX2. 整数序列 [-1, 3, -1, 1, 2]

最大加总序列为 3 - 1 + 1 + 2 = 5，虽然中间有负数，但也有正数可以相互抵销影响，直到加总的数字超过 原本正数 3 本身

那加总最大序列就会从 [3] 变成 [3, -1, 1, 2]，最大加总数字会从 3 变成 5

所以要能够让 加总最多的序列 能够大于目前数字的条件有

• 后方连接 正数 与 加总最多的序列（目前数字） 再加总，变成更大的 加总最多的序列
• 后方连接 负数，但后方也有其他的正数可以抵消这个负数的影响，直到后方的正数加总起来超过原本的加总最多的序列（目前数字），就可以找到最新的加总最多的序列

3. 纪录当前加总最多的总和

当 没有新的加总数字 超过 先前加总数字，原本的最大加总数字不变

当 有新的加总数字 超过 先前加总数字，取最大的数字当作 新的加总数字

直到最后的那个最大加总数字，就是能够找出的加总最多的序列总和

答案

JavaScript

/**
 * @param {number[]} numsList
 * @return {number}
 */
var maxSubArray = function(numsList) {
    // 最大子序列加总大小，预设是第 1 个数字
    // - 避免传入的数字只有 1 个负数，然后加总也没办法变成正数，所以预先设定加总是第 1 个
    // - e.g. [-1]
    let maxSubSum = numsList[0];
    // 计算后方加总数字
    let currentSum = 0;

    for (let i = 0; i < numsList.length; i++) {
        // 目前数字
        let currentNumber = numsList[i];
        if (currentSum < 0) {
            // 假如后方加总数字，没办法整体维持正数的话，表示加上这个数字没有任何帮助，直接重来砍掉重练
            currentSum = 0;
        }
        // 「目前加总数字」加上「目前数字」
        currentSum += currentNumber;
        // 取得目前加总数字最大的那个
        // - 如果「目前加总的数字」大于「之前最大加总数字」，表示「目前的子序列」可以取代「之前的子序列」
        // - 如果「目前加总的数字」小于或等于「之前最大加总数字」，表示「目前的子序列」要再加油，还没赢过之前的序列
        maxSubSum = Math.max(maxSubSum, currentSum);
    }

    return maxSubSum;
};

参考资料

• Maximum Subarray - LeetCode
• CS-Notes/Leetcode 题解 - 贪心思想.md at master · CyC2018/CS-Notes · GitHub
• Maximum Subarray - Amazon Coding Interview Question - Leetcode 53 - Python - YouTube