LeetCode:53. 最大子数组和 - Python

53. 最大子数组和

问题描述：

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

示例 1：

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

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

问题分析：

最近又遇到的老题目，很简单大家都知道是dp，但是如果真的是在面试环境上紧张了也许就漏了部分条件，不能AC，所以平时的基本功还是要打扎实的。具体思路：
假设dp[i]表示以数组nums[i]结尾的最大子数组和，那么：dp[i]=max{nums[i], dp[i−1]+nums[i]}，解释：dp[i] 的值很显然有两种情况，第1种情况：为上一个状态dp[i−1] 加上当前值nums[i]，第2种情况：从当前值nums[i]重新起一个序列(重新开始)，这两个种情况选择哪个呢？咱们求的最值吗？所以二者选取最大值。最后把整个dp遍历一般获取最大值即可。

Python3实现：

# @Time   :2023/08/24
# @Author :Liu
# 动态规划class Solution:def maxSubArray(self, nums):size = len(nums)if size == 0: return 0dp = [0 for _ in range(size)]dp[0] = nums[0]for i in range(1, size):dp[i] = max(nums[i], dp[i-1] + nums[i])return max(dp)

举一反三：

问题来了，可能很多面试官不按照这个讨论出来牌，如果把题目最后求解的要求改成子数组和的绝对值最大值那？仔细想想也不难，在维持一个和最小dp就可以了，最后结合两个dp的结果返回。

Python3实现：

# @Time   :2023/08/24
# @Author :Liu
# 动态规划class Solution:def maxSubArray2(self, nums):size = len(nums)if size == 0: return 0dpmax = [0 for _ in range(size)]dpmin = [0 for _ in range(size)]dpmax[0] = nums[0]dpmin[0] = nums[0]for i in range(1, size):dpmax[i] = max(nums[i], dpmax[i - 1] + nums[i])dpmin[i] = min(nums[i], dpmin[i - 1] + nums[i])return max(abs(max(dpmax)), abs(min(dpmin)))if __name__ == '__main__':solu = Solution()nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4, -10]print(solu.maxSubArray(nums))  # [-5, 4, -10] 11

声明： 总结学习，有问题或不当之处，可以批评指正哦，谢谢。
题目链接：https://leetcode.cn/problems/maximum-subarray/description/
参考链接：https://leetcode.cn/problems/maximum-subarray/solutions/9058/dong-tai-gui-hua-fen-zhi-fa-python-dai-ma-java-dai/