描述
给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
思路
- 错误思路,滑动窗口来解会有问题,左指针往右移动时不一定是最大和
- 分解问题,首先提个问题,什么是子数组,有左右边界且边界在nums数组边界范围内
- 第二个问题,如何统计子数组,遍历的时候,左边界可能位置的个数,那边这些位置到当前遍历下标的和的最大值,也就构成了当前下标为右边界的子数组的最大和
- 泛化思考,到第i个下标为止的连续子数组的最大和d[i]是如何构成的,即d[i-1]+nums[i],如果d[i-1]为负数,那nums[i]就是最大和
题解
class Solution:def maxSubArray(self, nums: List[int]) -> int:size = len(nums)if size == 0:return 0dp = [0 for _ in range(size)]dp[0] = nums[0]for i in range(1, size):if dp[i - 1] >= 0:dp[i] = dp[i - 1] + nums[i]else:dp[i] = nums[i]return max(dp)