动态规划解决最大子数组和问题_用动态规划算法解决最大子数组和问题,其时间复杂性为( )。

题目描述

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

示例 1：

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

示例 2：

输入：nums = [1]
输出：1

题目链接：. - 力扣（LeetCode）

思路1 动态规划

动态规划通常适用于具有重叠子问题和最优子结构性质的问题。在最大子数组和问题中，我们可以定义状态 dp[i] 表示以第 i 个元素结尾的最大子数组和。根据这个定义，我们可以得到状态转移方程：

• 当 i = 0 时，dp[0] = nums[0]；
• 当 i > 0 时，如果 dp[i-1] < 0，则 dp[i] = nums[i]；否则，dp[i] = dp[i-1] + nums[i]。

最终的答案即为 dp 列表中的最大值。

python代码

下面是基于上述思路实现的 Python 代码：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp=[]
        for i in range(len(nums)):
            if i==0:
                dp.append(nums[i])
                continue
            else:
                if dp[-1]<0:
                    dp.append(nums[i])
                else:
                    dp.append(dp[-1]+nums[i])
        return max(dp)

总结

通过动态规划算法，我们可以高效地解决最大子数组和的问题，时间复杂度为 O(n)，空间复杂度为 O(n)。这种方法利用了重叠子问题的特性，在遍历数组过程中不断更新当前最大子数组和，从而得到最终的结果。

思路2 

思路简介：将nums[i]改为原来nums前i项和， nums[x]-nums[y]则表示原nums从第x项到第y项元素之和（x<y)

1. 实现逻辑： 代码首先对给定的数组进行了求和操作，并将求和结果保存在变量sum中。接着使用enumerate函数遍历数组中的每个元素，同时累加元素的值到sum中，并将累加后的值赋给当前位置的元素。通过这一步骤，我们实现了将每个元素替换为从数组开头到该位置的所有元素的累加和。

   然后，定义了变量ans来保存最终的结果，初始值为第二个元素（nums[1]）。接下来，我们创建了两个空列表leftmin和rightmax。通过遍历数组，我们分别计算了左侧最小值和右侧最大值，并将它们分别存储在leftmin和rightmax列表中。

   最后，在一个循环中，我们使用max函数来比较右侧最大值减去左侧最小值（如果i-1>=0则使用leftmin[i-1]，否则使用0）和当前的ans，将较大的值赋给ans。这样我们就得到了连续子数组的最大差值。

2. 关键思路： 这段代码的关键思路是通过累加和数组和左右最值数组的计算，找出连续子数组的最大差值。通过不断更新变量ans，最终得到最大差值。

python代码

        if len(nums)==1:
            return nums[0]
        #将nums[i]变为原nums前i项和
        sum = 0
        for ind, val in enumerate(nums):
            sum+=val
            nums[ind]=sum
        
        #ans表返回值， leftmin[i]和rightmax[i]表示第i（不含）个数左边最小数，第i（含）个数右边最大数
        ans=nums[1]
        leftmin, rightmax=[], []
        _min=0
        _max=nums[-1]
 
        for ind, val in enumerate(nums):
            _min=min(_min, val)
            leftmin.append(_min)
        for ind, val in enumerate(nums[::-1]):
            _max=max(_max, val)
            rightmax.append(_max)
        rightmax=rightmax[::-1]
        
        for i in range(len(nums)):
            # rightmax与leftmin不可均用i，不然nums单调递减时会出错
            ans = max(rightmax[i]-(leftmin[i-1] if i-1>=0 else 0), ans)
 
        return ans

示例演示

 假设我们有一个数组nums = [4, 2, 9, 7, 5, 1, 6]。按照代码的逻辑，我们可以得到以下结果：

第一步，计算累加和数组： [4, 6, 15, 22, 27, 28, 34]

第二步，计算左侧最小值数组： [4, 2, 2, 2, 2, 1, 1]

第三步，计算右侧最大值数组： [34, 34, 34, 34, 34, 6, 6]

最后，根据循环，比较右侧最大值减去左侧最小值和当前的ans，并将较大的值赋给ans，得到最终的结果： ans = max(34-4, ans) = 30

因此，对于给定的数组nums，连续子数组的最大差值为30。

总结

通过分析这段代码，我们了解到了一种求解连续子数组最大差值的算法。通过累加和数组和左右最值数组的计算，我们可以得到连续子数组的最大差值。这个算法可以在某些问题中起到很好的作用，但也需要注意其局限性。希望本文对你理解这段代码的原理有所帮助！

结束语

感谢阅读本篇博客！希望本文能够对你理解和运用这段代码提供帮助。如果你对其他问题有任何疑问或者需要进一步的解释，请随时提问。谢谢！

详细题解：. - 力扣（LeetCode）