最大子数组和

53. 最大子数组和

给出了三种解决方案的代码实现，分别是：滑动窗口（1、2）、动态规划（3、4）以及前缀和（5）

class MaxSubArray:
    """
    53. 最大子数组和
    https://leetcode.cn/problems/maximum-subarray/description/
    """
    def solution(self, nums: List[int]) -> int:
        res = float('-inf')
        sum = 0
        for num in nums:
            sum += num
            res = max(res, sum)
            # 这样保证了最大子数组和必然是以正数开头的
            if sum < 0:
                sum = 0
        return res

    def solution2(self, nums: List[int]) -> int:
        """
        滑动窗口
        :param nums:
        :return:
        """
        left, right = 0, 0
        window_sum = 0
        res = float('-inf')
        while right < len(nums):
            # 扩大窗口并更新窗口内的元素和
            window_sum += nums[right]
            right += 1
            # 更新答案
            res = max(res, window_sum)

            # 判断窗口是否要收缩
            while window_sum < 0:
                window_sum -= nums[left]
                left += 1

        return res

    def solution3(self, nums: List[int]) -> int:
        """
        动态规划
        时间复杂度：O(n)
        空间复杂度：O(n)
        :param nums:
        :return:
        """
        n = len(nums)
        # dp[i] 记录以nums[i]为结尾的 最大子数组和
        dp = [0] * n
        # base case
        dp[0] = nums[0]
        # 状态转移方程，要么自成一派，要么和前面的数组合并
        for i in range(1, n):
            dp[i] = max(dp[i-1]+nums[i], nums[i])

        res = float('-inf')
        for i in range(n):
            res = max(res, dp[i])

        return res

    def solution4(self, nums: List[int]) -> int:
        """
        动态规划改进，可以看出来dp[i] 只和dp[i-1]的状态有关，可进一步压缩空间
        时间复杂度：O(n)
        空间复杂度：O(n)
        :param nums:
        :return:
        """
        n = len(nums)
        res = float('-inf')
        # base case
        dp_0 = nums[0]
        # 状态转移方程，要么自成一派，要么和前面的数组合并
        for i in range(1, n):
            dp_1 = max(dp_0 + nums[i], nums[i])
            dp_0 = dp_1

            # 顺便更新结果
            res = max(res, dp_1)

        return res

    def solution5(self, nums: List[int]) -> int:
        """
        前缀和
        pre_sum[i]表示nums[0...i-1]的累加和
        :param nums:
        :return:
        """
        n = len(nums)
        pre_sum = [0] * (n+1)
        for i in range(1, n+1):
            pre_sum[i] = pre_sum[i-1] + nums[i-1]

        res = float('-inf')
        min_val = float('inf')
        for i in range(n):
            # 维护 minVal 是 preSum[0..i] 的最⼩值
            min_val = min(min_val, pre_sum[i])
            # 以 nums[i] 结尾的最⼤⼦数组和就是 preSum[i+1] - min(preSum[0..i])
            res = max(res, pre_sum[i+1]-min_val)

        return res