题解 | #连续子数组的最大和(二)#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param array int整型一维数组 
 * @return int整型一维数组
 */
export function FindGreatestSumOfSubArray(array: number[]): number[] {
    //1. 动态规划来确定dp为连续子元素之和，i为元素，状态转移方程为dp[i] = Math.max(dp[i-1] + array[i],array[i])
    //2. 然后控制范围，滑动范围,分情况来进行滑动这个区间
    const dp = []
    dp[0] = array[0]
    let maxsum  = array[0]
    let left = 0,right = 0//滑动的范围
    let resl = 0,resr = 0//最长的区间范围
    for(let i = 1;i < array.length;i++){
        right++
        dp[i] = Math.max(dp[i-1]+array[i],array[i])
        //控制范围,更新左边的范围
        if(dp[i-1]+array[i] < array[i]){
            left = right
        }
        //更新最大值:当前的连续子数组大于最大的值
        if(dp[i] > maxsum || dp[i] === maxsum && (right - left + 1) > (resr - resl + 1)){
            maxsum = dp[i]
            resl = left
            resr = right
        }
    }
    //找到区间了，取值
    return array.slice(resl,resr+1)
}