0%

找具有最大和的连续子数组

发表于 阅读次数：

题目：

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

示例:

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

解题思路：

利用动态规划的思想去解决问题，动态规划需要遍历数组，但这里并不是从每一个结点开始往后遍历找最大，而是把当前结点当做累加的最后一个结点，如以当前结点为最后一个则当前可以到达的最大值为dp[i]， 则观察dp[i-1],

如果dp[i-1]>0，则dp[i]=dp[i-1]+nums[i],否则dp[i]从当前从新开始。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        size=len(nums)
        dp=[0 for i 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)