leetcode | 53.最大子数组和

53.最大子数组和

题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。

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

题目链接

代码

class Solution(object):
    def maxSubArray(self, nums):
        """
        动态规划
        
        用f(i)代表以第i个数结尾的连续子数组的最大和，那么我们的目标就是求
                            max{f(i)},0<=i<=n-1
        如何求 f(i) 呢？
        我们可以考虑 nums[i] 单独成为一段还是加入 f(i−1)对应的那一段，这取决于 nums[i] 和 f(i−1)+nums[i] 的大小，
        我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：
                            f(i)=max{f(i-1)+nums[i], nums[i]}
        :type nums: List[int]
        :rtype: int
        """
        # pre = 0
        # maxAns = nums[0]
        # for x in nums:
        #     pre = max(pre + x, x)
        #     maxAns = max(maxAns, pre)
        # return maxAns
        
        fi_array = [nums[0]]
        for i in range(1, len(nums)):
            fi_array.append(max(fi_array[i-1]+nums[i], nums[i]))
        return max(fi_array)
    
    def maxSubArray1(self, nums):
        """
        动态规划
        
        若前一个元素大于0，则将其加到当前元素上
        """
        for i in range(1, len(nums)):
            # 若前一个元素大于0，则将其加到当前元素上
            if nums[i - 1] > 0:
                nums[i] += nums[i-1]
        return max(nums)  # 返回修改过的数组中的最大值
    
    
    def maxSubArray2(self, nums):
        """
        贪心算法
        
        # 若当前指针所指元素之前的和小于0，则丢弃当前元素之前的数列
        """
        if not nums:  # 设置边界条件（列表为空）
            return -2147483648
        cur_sum = max_sum = nums[0]  # 当前和和最大和设置为列表第一个元素
        for i in range(1, len(nums)):
            # 若当前指针所指元素之前的和小于0，则丢弃当前元素之前的数列
            cur_sum = max(nums[i], cur_sum+nums[i])
            
            # 将当前和与最大和作比较，取最大
            max_sum = max(cur_sum, max_sum)
        
        return max_sum


if __name__ == "__main__":
    slt = Solution()
    nums = list([-2, 1, -3, 4, -1, 2, 1, -5, 4])
    res = slt.maxSubArray(nums)
    # res = slt.maxSubArray1(nums)
    print(res)