【动态规划专题】剑指 Offer 42. 连续子数组的最大和-跟着帅地玩副业，开拓第二曲线PlayOffer

Gg 普通 2023年8月4日下午9:34

class Solution {
    // 1、dp[i] 的含义
    // 为 包含nums[i] 在内的最大连续子数组的最大和
    // 2、确定dp方程
    // dp[i] = nums[i] + dp[i-1] if(dp[i-1] > 0) 
    // dp[i] = nums[i] if dp(i-1) == 0
    // 3、dp初始化
    // 这里无所谓
    // 4、确定遍历顺序
    // 这里无所谓
    // 5、举例推导
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for(int i = 1; i < nums.length; i ++){
            if(dp[i-1] > 0){
                dp[i] = dp[i-1] + nums[i];
            }else{
                dp[i] = nums[i];
            }
        }
        int res = dp[0];
        for(int i : dp){
            res = Math.max(res,i);
        }
        return res;
    }
}
class Solution {
    // 优化空间版
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        for(int i = 1; i < nums.length; i ++){
            if(nums[i-1] > 0){
                nums[i] += nums[i-1];
            }
            res = Math.max(nums[i],res);
        }
        return res;
    }
}

0 赞同 0 条回复

宁永久会员 2023年3月14日上午11:30

最简单的动态规划问题，初始化为nums[0]

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int dp = nums[0];
        for(int i = 1; i < nums.length; i++){
            dp = Math.max(nums[i] + dp, nums[i]);
            max = Math.max(dp, max);
        }
        return max;
    }
}

0 赞同 0 条回复

lucca 普通 2023年1月18日下午1:17

DP

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

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        f[0] = nums[0];
        int max = f[0];
        for (int i = 1; i < n; i++) {
            f[i] = Math.max(0, f[i - 1]) + nums[i];
            max = Math.max(max, f[i]);
        }
        return max;
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月18日上午11:49

# 一位数组推导公式 ： dp[n] = max(nums[n],nums[n]) + dp[n-1]
def maxSubArray(nums: list[int]) -> int:
    if len(nums) == 1:
        return nums[0]

    m = len(nums)
    # 定义dp[n] 为以nums[n]为结尾的连续子树组最大和
    # 找到就是dp中的最大值
    dp = [None] * m

    # 初始化
    dp[0] = nums[0]
    max_ = nums[0]

    for n in range(1,m):
        dp[n] = max(nums[n],nums[n] + dp[n-1])
        max_ = max(max_,dp[n])

    print(dp)
    return max_


# 优化 将dp变成一个单变量
def maxSubArray1(nums: list[int]) -> int:
    if len(nums) == 1:
        return nums[0]

    m = len(nums)
    # 定义dp[n] 为以nums[n]为结尾的连续子树组最大和
    # 找到就是dp中的最大值
    dp = nums[0]

    # 初始化
    max_ = nums[0]

    for n in range(1,m):
        dp= max(nums[n],nums[n] + dp)
        max_ = max(max_,dp)
    return max_

0 赞同 0 条回复

@ 普通 2022年12月17日上午10:53

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

**时间复杂度：O(1)**

```java
class Solution {
    public int maxSubArray(int[] nums) {
        int dp = nums[0];
        int max = nums[0];

        for (int i = 1; i < nums.length; i++) {
            dp = Math.max(dp + nums[i], nums[i]);
            max = Math.max(max, dp);

        }

        return max;

    }
}

```

0 赞同 0 条回复

Error 普通 2022年12月4日下午10:30

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

时间复杂度 O(n)

思路：当前一个数小于0时，不去加，大于0就加

0 赞同 0 条回复

symbol 普通 2022年12月3日上午7:52

func maxSubArray(nums []int) int {
    // 设动态规划列表dp,dp[i] 代表以元素nums[i]为结尾的连续子数组最大和
    // 以某个数作为结尾，意思就是这个数一定会加上去，那么要看的就是这个数前面的部分要不要加上去。大于零就加，小于零就舍弃。
    dp := []int{nums[0]}
    maxValue := dp[0]
    // 转移方程:
    // (1)当 dp[i - 1] > 0 时：执行 dp[i] = dp[i-1] + nums[i]
    // (2)当 dp[i−1]≤0 时：执行 dp[i] = nums[i]
    for i := 1; i < len(nums); i++ {
        dp = append(dp, math.MinInt32)
        if dp[i-1] <= 0 {
            dp[i] = nums[i]
        } else {
            dp[i] = dp[i-1] + nums[i]
        }
        if maxValue < dp[i] {
            maxValue = dp[i]
        }
    }
    return maxValue
}

0 赞同 0 条回复

派大星普通 2022年12月2日下午10:59

class Solution {
//时间复杂度O(n)
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int dp = nums[0];
        int max = nums[0];
        for(int i = 1;i < len;i++){
            dp = Math.max(0,dp) +nums[i];
            max = Math.max(max,dp);
        }
        return max;
    }
}

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:32

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //动态规划，不断更新每个元素的值
        int maxvalue = nums[0];
        int sum = 0;
        for(int i = 1; i < nums.size();i++){
            nums[i] += max(nums[i-1],0);
            maxvalue=max(nums[i],maxvalue);
        }
        return maxvalue;
    }
};

0 赞同 0 条回复

T 普通 2022年11月30日下午8:29

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = nums[0];
        for(int i = 1; i < nums.length; i++) {
            //dp[i] 表示元素nums[i]结尾的连续子数组最大和
            dp[i] = Math.max(nums[i], nums[i] + dp[i-1]);
            if(dp[i] > max) max = dp[i];
        }
        return max;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2022年11月26日下午7:35

C++
动态规划
class Solution {
public:
int maxSubArray(vector& nums) {
int len = nums.size();
int dp = nums[0];
if(len 1) return dp;
int maxn = dp;
for(int i = 1; i < len; ++i) {
dp = max(nums[i], dp+nums[i]);
maxn = max(dp, maxn);
}
return maxn;
}
};

0 赞同 0 条回复

y 普通 2022年11月26日下午3:29

var maxSubArray = function(nums) {
 let max = nums[0];
 let pre = 0;
 for (let num of nums) {
     pre = Math.max(pre + num, num);
     max = Math.max(pre, max)
 }
 return max;
};

时间：O(n)
空间：O(1)

0 赞同 0 条回复

你有点可爱喔普通 2022年11月25日下午4:46

时间复杂度O(n）

class Solution {
    public int maxSubArray(int[] nums) {
        int dp [] = new int[nums.length];
        dp [0] = nums[0];
        int max = nums[0];
        for (int i = 1;i <nums.length;i++){
            dp [i] = Math.max(dp[i-1]+nums[i],nums[i]);
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}

0 赞同 0 条回复

just 普通 2022年11月24日下午7:44

//最简单的dp问题了
class Solution {
public:
int maxSubArray(vector& nums) {
for(int i=1;i<nums.size();++i) nums[i]=max(nums[i],nums[i]+nums[i-1]);
int res=INT32_MIN;
for(int cur:nums) res=max(res,cur);
return res;

};

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月24日上午12:18

时间复杂度O(n)空间复杂度O(1)

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int dp = nums[0];
        int max = nums[0];
        for(int i = 1;i < len;i++){
            dp = Math.max(0,dp) +nums[i];
            max = Math.max(max,dp);
        }
        return max;
    }
}

0 赞同 0 条回复

So 普通 2022年11月23日下午9:22

class Solution {
    public int maxSubArray(int[] nums) {
        int dp = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp = Math.max(dp + nums[i], nums[i]);
            max = Math.max(max, dp);
        }
        return max;
    }
}

时间：O(n)，空间：O(1)

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月23日下午8:50

时间复杂度为O（n），空间复杂度为O（1）

class Solution {
    public int maxSubArray(int[] nums) {
        int dp = nums[0];
        int res = nums[0];
        for(int i = 1;i < nums.length;i++){
            dp = Math.max(nums[i],dp+nums[i]);
            res = Math.max(res,dp);
        }
        return res;
    }
}

0 赞同 0 条回复

Tolkien 永久会员 2022年11月23日下午2:57

/**
     * 1. dp数组的含义：以nums[i]为结尾的连续子数组的最大和
     * 2. 关系式：当dp[i-1]>0时，dp[i] = nums[i],
     *    当dp[i-1]<0时，dp[i] = dp[i-1]+nums[i])
     * 3. 初始化: dp[0] = nums[0]
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public static int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];

        for (int i = 1; i < nums.length; i++) {
            dp[i] = dp[i-1] > 0 ? dp[i-1]+nums[i] : nums[i];
            max = Math.max(max, dp[i]);
        }

        return max;
    }
}

0 赞同 0 条回复

青木普通 2022年11月22日下午10:55

/**
    本来分成了两部分，
    一个是前面相加的数大于0的情况，只需要继续加（只要大于0就有意义，小于0就没意义了），
    然后保存最大值就可以了
    一个是小于0的情况，取当前值和前面相加的值较大的那个，再继续
    结果后来发现这两行代码是一样的0.0

    时间O(n)
    空间O(1)
 */

class Solution {
    public int maxSubArray(int[] nums) {
        int ans = nums[0];
        int dp = 0;

        for(int num : nums){
            dp = Math.max(num, dp+num);
            ans = Math.max(ans, dp);
        }
        return ans;
    }
}

0 赞同 0 条回复

【动态规划专题】剑指 Offer 42. 连续子数组的最大和

共以下 19 个回答

DP

# 回答此问题取消回复

【动态规划专题】剑指 Offer 42. 连续子数组的最大和

共以下 19 个回答

DP

# 回答此问题 取消回复

# 回答此问题取消回复