LeetCode-53 最大子序和 --- Python代码实现及详解

朱雀 2020-10-31 18:27 508阅读 0赞

### 题目： ###

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

示例:

输入: \[-2,1,-3,4,-1,2,1,-5,4\],

输出: 6

解释: 连续子数组 \[4,-1,2,1\] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

### 思路： ###

DP算法是解决**多阶段决策过程**最优化问题的一种常用方法。

** 多阶段决策过程（multistep decision process）**是指这样一类特殊的活动过程，过程可以按时间顺序分解成若干个相互联系的阶段，在每一个阶段都需要做出决策，全部过程的决策是一个决策序列。

**动态规划（dynamic programming）**算法是解决多阶段决策过程最优化问题的一种常用方法，难度比较大，技巧性也很强。利用动态规划算法，可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。

动态规划算法的**基本思想**是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果，与贪婪算法不同的是，在贪婪算法中，每采用一次贪婪准则，便做出一个不可撤回的决策；而在动态规划算法中，还要考察每个最优决策序列中是否包含一个最优决策子序列，即问题是否具有最优子结构性质。

### 编码实现： ###

方法一：普通方法

class Solution:
        def maxSubArray(self, nums: List[int]) -> int:
            sum = 0
            max_sub_sum = nums[0]
            for num in nums:
                sum += num
                if sum > max_sub_sum:
                    max_sub_sum = sum
                if sum < 0:
                    sum = 0
            return max_sub_sum

方法二：动态规划法

class Solution:
        def maxSubArray(self, nums: List[int]) -> int:
            # 动态规划法
            le = len(nums)
            for i in range(1, le):
                # 前i-1个最大的结果已经存在i-1中，每次都可看做是两个数相加
                submax = max(nums[i]+nums[i-1], nums[i])
                # 把每次最大的结果赋值给当前值，然后继续下一个两数相加
                nums[i] = submax
            return max(nums)