Leetcode 53.最大子数组和题解

题目描述

题目:最大子数组和

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

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

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

解题思路

不如先从递归开始想

nums[i] = dfs(i-1)+nums[i],nums[i]

每个数字由dfs(i-1)+nums[i] 是把前面的数字加起来

nums[i] 是还原 代表前面的数字相加之后比原数字小

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:

        # 每个数字可以选或者不选
        def dfs(i):
            if i < 0: return 0
            nums[i] = max(dfs(i-1)+nums[i],nums[i])
            return nums[i]
        dfs(len(nums)-1)
        return max(nums)

class Solution {
public:

    int dfs(vector<int> & nums, int i){
        if (i < 0){return 0;}
        nums[i] = max(nums[i],nums[i]+dfs(nums,i-1));
        return nums[i];
    }

    int maxSubArray(vector<int>& nums) {
        dfs(nums,nums.size()-1);
        int ans = 0;
        for(int i = 0; i < nums.size(); i++){
            ans = max(ans,nums[i]);
        }
        return ans;
    }
};

但是你提交之后 用时有点长 内存消耗也很大 虽然能过

现在来把他一比一翻译

dp[i] = max(dp[i-1]+nums[i],nums[i])
nums[i] = max(dfs(i-1)+nums[i],nums[i])

dp[0] = nums[0]

翻译之后 就能改成迭代形式了 以下是迭代写法 但还不是最优写法

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

class Solution {
public:
    int dp[100001];
    int maxSubArray(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++){
            dp[i] = -10000;
        }
        dp[0] = nums[0];
        int ans = max(-10000,dp[0]);
        for(int i = 1; i < nums.size(); i++){
            dp[i] = max(dp[i-1]+nums[i],nums[i]);
            ans = max(ans,dp[i]);
        }
        return ans;
    }
};

现在已经是迭代了 那有没有什么办法能把空间优化到O(1)呢

我们只需要用变量维持dp[i-1]就行了

以下是最终代码

示例代码

# 时间复杂度:O(n)
# 空间复杂度:O(1)
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = max(-10000,nums[0])
        for i in range(1,len(nums)):
            nums[i] += max(0,nums[i-1])
            ans = max(ans,nums[i])
        return ans

// 时间复杂度:O(n)
// 空间复杂度:O(1)
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = max(-10000,nums[0]);
        for(int i = 1; i < nums.size(); i++){
            nums[i] += max(0,nums[i-1]);
            ans = max(ans,nums[i]);
        }
        return ans;
    }
};