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

动态规划，定义 dp 数组, 其中 dp[i] 表示 array[0:i] 连续子数组的最大和; 转移方程为： (1) dp[i] = dp[i - 1] + array[i] 当 array[i] + dp[i - 1] >= array[i] (2) dp[i] = array[i] 当 array[i] + dp[i - 1] < dp[i - 1] 因为求的是连续子数组,则 dp[i] 的值与 dp[i - 1] 和 array[i] 有关, 即 dp[i - 1] + array[i] 较大时, dp[i] 由 dp[i - 1] 转移,否则 dp[i] 为当前值 再定义子数组长度数组 indexs, 其值 indexs[i] 表示 dp[i] 代表的子数组中数组的个数, 则 dp 中大值对应索引 i 的 indexs[i] 表示子数组个数，取其中最大的值得出最终的子数组

class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> List[int]:
        # write code here
        dp, indexs = [0 for _ in range(len(array))], [0 for _ in range(len(array))]
        dp[0], indexs[0] = array[0], 1
        for i in range(1, len(array)):
            if array[i] + dp[i - 1] >= array[i]:
                dp[i] = dp[i - 1] + array[i]
                indexs[i] = indexs[i - 1] + 1
            else:
                dp[i] = array[i]
                indexs[i] = 1
        max_v = max(dp)
        max_l, idx = 0, -1
        for i in range(len(array)):
            if dp[i] == max_v:
                if indexs[i] > max_l:
                    idx = i
                    max_l = indexs[i]
        return array[idx - max_l + 1:idx + 1]