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

hi 普通 2023年11月10日上午11:47

递推（自底向上）方程和BFS（自顶向下）方程一样

class Solution {
public:
    int maxSales(vector<int>& sales) {
        int f[100010];
        memset(f, 0, sizeof f);
        int res = -2e9;

        for(int i = 1; i <= sales.size(); i++){
            f[i] = max(sales[i - 1], f[i - 1] + sales[i - 1]);
            if(f[i] > res) res = f[i];
        }

        return res;
    }
};

0 赞同 0 条回复

Marshan 普通 2023年8月27日下午8:37

相对简单,优化成单变量的时候注意顺序

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // vector<int> dp(nums.size(),0);

        // dp[0] = nums[0];
        if(nums.size() == 1){
            return nums[0];
        }
        int temp = nums[0],res = nums[0];

        // temp = nums[0];

        for(int i = 1;i < nums.size();++i){
            temp = max(temp + nums[i],nums[i]);
            res = max(res,temp);
        }



        // for(int item:dp){
        //     res = max(res,item);
        // }

        return res;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年8月21日上午11:05

class Solution {
    public int maxSubArray(int[] nums) {
        // 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
        //输出: 6
        //解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        return max;
    }
}

0 赞同 0 条回复

人生何处不青山普通 2023年8月19日下午11:42

ts写的

function maxSubArray(nums: number[]): number {
    let tmp = new Array(nums.length);
    let res = nums[0];
    tmp[0] = nums[0];
    for(let i = 1; i < nums.length;i++){
        tmp[i] = Math.max(nums[i] + tmp[i-1],nums[i]);
        res = Math.max(res,tmp[i]);
    }
    return res;
};

0 赞同 0 条回复

Mby 普通 2023年8月14日下午6:40

class Solution {
    public int maxSubArray(int[] nums) {
        int dp = nums[0];
        int max = nums[0];
        //刷新dp之前，dp相当于是dp[i - 1], 刷新之后Dp就是dp[i]
        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 条回复

北辰普通 2023年8月14日上午10:18

public class 连续子数组的最大和 {

    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxSubArray(nums));
    }

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

0 赞同 0 条回复

#00456B 普通 2023年8月10日下午2:21

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if(n == 0){
            return 0;
        }
        vector<int> dp(n);
        dp[0] = nums[0];
        int ans = nums[0];
        for(int i = 1; i < n; i++){
            //状态转移方程就是dp[i] = max(nums[i], nums[i] + dp[i - 1]);
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

0 赞同 0 条回复

NullPointerException 普通 2023年8月7日下午8:04

class Solution {
public int maxSubArray(int[] nums) {
//找到每个位子最大子数组之和要么能连续要么取自己
int dp[]=new int[nums.length+1];
Arrays.fill(dp,Integer.MIN_VALUE+1);
int max =nums[0];
dp[1]=nums[0];
for(int i=2;i<=nums.length;i++)
{
dp[i]=Math.max(dp[i-1]+nums[i-1],nums[i-1]);
max = Math.max(max,dp[i]);
}
return max;
}
}

0 赞同 0 条回复

AD钙奶普通 2023年8月7日上午11:35

dp : 以第i个数为结尾的连续子数组的和

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

0 赞同 0 条回复

长河呼叫黄江普通 2023年8月5日下午4:31

8.5
Day26：下面是代码

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0;
        int res = nums[0];
        for(int num : nums){
            pre = Math.max(pre + num, num);
            res = Math.max(pre, res);
        }
        return res;
    }
}

0 赞同 0 条回复

阿尚普通 2023年8月5日下午1:56

//动态规划
//O(n)
//O(n)
class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = nums[0];
        for(int i = 1; i < nums.length; i++){
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            res = Math.max(res, dp[i]);
        }

        return res;
    }
}

//贪心
//O(n)
//O(1)
class Solution {
    public int maxSubArray(int[] nums) {
        int res = Integer.MIN_VALUE;
        int sum = 0;

        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            res = sum > res ? sum : res;
            if(sum < 0){
                sum = 0;
            }
        }
        return res;
    }
}

0 赞同 0 条回复

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

共以下 11 个回答

# 回答此问题取消回复

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

共以下 11 个回答

# 回答此问题 取消回复

# 回答此问题取消回复