Jianbo Dai's

mq001.最大子序和

 
  • Oct 25, 2020

题目链接

这题我做过，就是lc053。首先讲一下第一种做法是用动态规划法，这样的时间复杂度是O（N），该实现如下所示。这个实现的空间复杂度是O（N），就如同典型的一维dp一样，可以将空间优化到O（1）。一种做法是用其他变量来暂时保存某个时刻的最大值，或者我们注意到dp的过程中只与res[i-1]和nums[i]有关，我们可以用nums作为dp数组这样呀也能实现空间复杂度的优化。另外，这题也可以用分治的思想去解决但是时间复杂度为O（NlogN），空间复杂度为O（logN），都不如动态规划来的好所以就不写了。

class Solution:
    def maxSubArray1(self, nums) -> int:
        res = [0]*len(nums)
        res[0] = nums[0]
        for i in range(1, len(nums)):
            res[i] = max(nums[i], res[i-1] + nums[i])
        return max(res)

    def maxSubArray2(self, nums) -> int:
        for i in range(1, len(nums)):
            nums[i] += max(0, nums[i-1])
        return max(nums)
Search