题解 | #没有重复项数字的全排列#

正确写法（动态规划完每次保留最大值）：

class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> int:
        # write code here
        dp = []
        maxsum = array[0]
        l = len(array)
        for i in range(0, l):
            if i == 0:
                dp.append(array[i])
            else:
                dp.append(max(dp[i - 1] + array[i], array[i]))
                maxsum = max(maxsum, dp[i])
        return maxsum

错误写法（单纯用一个dp无法穷举所有的情况）：

class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> int:
        # write code here
        dp = []
        l = len(array)
        for i in range(0, l):
            if i == 0:
                dp.append(array[i])
            elif array[i] >= 0 and array[i - 1] >= 0:
                dp.append(dp[i - 1] + array[i])
            elif array[i] >= 0 and array[i -1] < 0:
                dp.append(max(dp[i - 1] + array[i - 1] + array[i], array[i]))
            elif array[i] < 0:
                dp.append(max(dp[i - 1], array[i]))
        return dp[-1]