LeetCode刷题（python版）——Topic53最大子数组和

一、题设

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

子数组 是数组中的一个连续部分。

示例 1：

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

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

二、基本思路

        这题用动态规划

        借助动态数组dp，dp[i]表示的是前i个元素的最大和，那么dp[i]的生成就要依赖于dp[i-1]：

        （1）当dp[i-1] > 0 时，即类似[1,2,1,4,5]这种情况，dp[i]的值就等于之前的dp[i-1] + 当前元素nums[i] , 也可以看作是当前范围的扩大.

        （2）当dp[i-1] <= 0 时，如果再按（1）加上nums[i]，那么这个值是肯定小于或等于nums[i]的，所以还不如不加，最大和就是他自己nums[i].

        故动态规划的状态转移方程如下：

三、代码实现

    def maxSubArray(self, nums):
        # DP[i] 代表第i个元素之前最大的排列和
        dp = [0 for _ in range(len(nums))]
        dp[0] = nums[0]
        for i in range(1,len(nums)):
            if dp[i-1] > 0:
                dp[i] = dp[i-1] + nums[i]
            else:
                dp[i] = nums[i]
        return max(dp)

四、效率总结