输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

输入：nums = [1]
输出：1

输入：nums = [5,4,-1,7,8]
输出：23

function maxSubArray(nums: number[]): number {
    // 可以用滑动窗口解决。
    // 如果纳入下个数，导致窗口和小于0，就直接抛弃整个窗口
    // 如果下个数是正数，则无条件添加，这题并不需要得到序列，所以其实不需要slow
    let slow = -1, fast = -1
    let sum = 0
    let res = -Infinity
    const n = nums.length
    while(fast + 1 < n){
        if(sum < 0){ // 防止数组中只有小于0的数字
            // 只会有一个元素
            fast++
            slow++
            sum = nums[fast]
        }else if(sum + nums[fast + 1] < 0){
            // 抛弃整个窗口
            fast++
            slow = fast
            sum = nums[fast]
        }else if(sum + nums[fast + 1] >= 0){
            // 下个数纳入后仍窗口和大于0
            // 直接划入窗口
            fast++
            sum += nums[fast]
        }
        res = Math.max(res, sum)
    }
    return res
};

function maxSubArray(nums: number[]): number {
    // 分治法
    // 整个序列自顶向下逐个拆解成左右区间
    // 直到区间被拆解成1个数字
    /**
        对每个区间维护四个值
        lSum 表示 [l,r] 内以 l 为左端点的最大子段和
        rSum 表示 [l,r] 内以 r 为右端点的最大子段和
        mSum 表示 [l,r] 内的最大子段和
        iSum 表示 [l,r] 的区间和
     */
     const helper = (l: number, r: number): {
        lSum: number
        rSum: number
        mSum: number
        iSum: number
     } => {
        if(l === r){
            // 区间只有一个元素时
            return {
                lSum: nums[l],
                rSum: nums[l],
                mSum: nums[l],
                iSum: nums[l],
            }
        }
        const mid = Math.floor((l + r) / 2)
        const lSub = helper(l, mid) // 求左边序列的四个状态
        const rSub = helper(mid + 1, r) // 求右边序列的四个状态

        // 合并后的序列的左端最大和 = max(左序列的左端最大和， 左序列的总和 + 右序列的左端最大和)右端序列最大和同理
        const lSum = Math.max(lSub.lSum, lSub.iSum + rSub.lSum)
        const rSum = Math.max(rSub.rSum, rSub.iSum + lSub.rSum)
        // 序列总和
        const iSum = lSub.iSum + rSub.iSum
        // 最大字段和原理如上图
        const mSum = Math.max(Math.max(lSub.mSum, rSub.mSum), lSub.rSum + rSub.lSum);
        return {
            lSum,
            rSum,
            iSum,
            mSum
        }
     }
     return helper(0, nums.length - 1).mSum
};

var maxSubArray = function(nums) {
    let pre = 0, maxAns = nums[0];
    nums.forEach((x) => {
        pre = Math.max(pre + x, x);
        maxAns = Math.max(maxAns, pre);
    });
    return maxAns;
};