leetcode:53. 最大子数组和

53. 最大子数组和

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

子数组 是数组中的一个连续部分。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

加粗样式提示：

1 <= nums.length <= 1 0 5 10^5 105 − 1 0 4 -10^4 −104 <= nums[i] <= 1 0 4 10^4 104

解法

动态规划：四个步骤： 问题定义 状态转移方程 初始条件和边界情况 确定计算顺序（自顶向下，还是自下向上）

问题定义： 连续的子数组和，假设用dp[i]表示以下标i结尾的长度，最终遍历完成后得到的dp表示以每个元素结尾时候的最大连续子数组和。这里最后一个元素不是最终结果，是求列表中的最小值

状态转移方程：

d p [ i ] = d p [ i − 1 ] + n u m s [ i ] , i f d p [ i − 1 ] > 0 dp[i] = dp[i-1] + nums[i], if dp[i-1] > 0 dp[i]=dp[i−1]+nums[i],ifdp[i−1]>0 d p [ i ] = n u m s [ i ] , o t h e r s dp[i] = nums[i], others dp[i]=nums[i],others 大致思想就是如果前面的元素和为负数，那么本元素就不考虑前面的元素和了，直接从自身元素开始。

初始化条件和边界条件

dp[0] = nums[0]

确定计算顺序: 这个是从下向上的方向计算即可

代码实现

动态规划

python实现

class Solution {
          
   
public:
    int maxSubArray(vector<int>& nums) {
          
   
        int n = nums.size();
        if (n == 1) return nums[0];
        vector<int> dp (n, 0);
        dp[0] = nums[0];
        for (int i=1; i<n; i++) {
          
   
            if (dp[i-1] > 0)
                dp[i] = dp[i-1] + nums[i];
            else
                dp[i] = nums[i];
        }
        return *max_element(dp.begin(), dp.end());
    }
};

c++实现

class Solution {
          
   
public:
    int maxSubArray(vector<int>& nums) {
          
   
        int n = nums.size();
        if (n == 1) return nums[0];
        vector<int> dp (n, 0);
        dp[0] = nums[0];
        for (int i=1; i<n; i++) {
          
   
            if (dp[i-1] > 0)
                dp[i] = dp[i-1] + nums[i];
            else
                dp[i] = nums[i];
        }
        return *max_element(dp.begin(), dp.end());
    }
};

这里dp也可以为原始数组nums，如果能够进行修改原始列表的话，空间复杂度为 O ( 1 ) O(1) O(1)

for i in range(1, n):
            if nums[i-1] > 0:
                nums[i] = nums[i-1] + nums[i]
        return max(nums)

复杂度分析

时间复杂度： O ( N ) O(N) O(N) 空间复杂度： O ( N ) O(N) O(N)

动态规划优化成两个变量

由于状态的改变只与前一个元素有关，我们只需要保存最近的元素状态即可，以及一个最大值 python实现

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]

        max_ans = nums[0]
        pre_val = nums[0]
        for num in nums[1:]:
            pre_val = max(pre_val+num, num)
            max_ans = max(pre_val, max_ans)
        return max_ans

c++实现

class Solution {
          
   
public:
    int maxSubArray(vector<int>& nums) {
          
   
        int n = nums.size();
        if (n == 1) return nums[0];

        int max_val = nums[0];
        int prev_val = 0;
        for (int num: nums) {
          
   
            prev_val = max(prev_val+num, num);
            max_val = max(prev_val, max_val);
        }
        return max_val;
    }
};

复杂度分析

时间复杂度： O ( N ) O(N) O(N) 空间复杂度： O ( 1 ) O(1) O(1)

参考