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

本问题对应课程链接：剑指offer刷题第三期

要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi

更新于 3 年前 115 17

共以下 17 个回答

招舟子普通 2023年12月6日下午12:35
class Solution {
public int maxSales(int[] sales) {
int[] dp = new int[sales.length];
dp[0]=sales[0];
int max =sales[0];
for(int i=1;i<sales.length;i++){
dp[i]=Math.max(sales[i],dp[i-1]+sales[i]);
max = Math.max(dp[i],max);
}
return max;
```
}
```
}
时间空间均是on可优化空间到o1
0 赞同 0 条回复

登录以回复
九号球普通 2023年12月2日下午8:23

“`java
class Solution {
public int maxSales(int[] sales) {
//dp[i]表示以第i个数结尾的连续天数的最高销售额， db[i] = Math.max(dp[i – 1] + sales[i], sales[i])
int max = sales[0];
int pre = 0;
for (int i = 1; i < sales.length; i++) { pre = Math.max(pre + sales[i], sales[i]); max = Math.max(max, pre); } return max; } }

0 赞同 0 条回复

登录以回复

张开怀普通 2023年7月23日下午10:04

class Solution{
public:
       int maxSubArray(vector<int>& nums){
              int dp = nums[0];
              int max_ = nums[0];        // 避免使用C++中的关键字max

              // 刷新dp之前，dp相当于是dp[i-1],刷新之后，Dp就是dp[i]
              for(int i=1;i< nums.size();i++){
                     dp = max(dp + nums[i],nums[i]);
                     max_ = max(max_,dp);
              }
              return max_;
       }

};

0 赞同 0 条回复

Dsjh 普通 2023年7月22日下午11:30

MY

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // f[n]表示以n为结尾的子数组的最大和
        // f[n-1] <= 0时，f[n] = ns[n];
        // f[n-1] >= 0时，f[n] = ns[n] + f[n-1];
        int pre = nums[0], ans = nums[0];
        for(int i=1;i<nums.size();i++){
            pre = pre < 0 ? nums[i] : pre + nums[i];
            ans = max(ans,pre);
        }
        return ans;
    }
};

0 赞同 0 条回复

BOZ 普通 2023年7月22日上午10:19

【思路】利用DP算法，dp[i]为包括了以nums[i]为结尾的最大连续子序列，并做了优化，使得空间复杂度为O(1)
【复杂度】时间复杂度O(n)，空间复杂度O(1)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // dp[i] is the max sum of subset of nums[x...i]
        size_t n = nums.size();
        int last = nums[0];
        int max = last;
        for (int i = 1; i < n; i++) {
            last = std::max(last + nums[i], nums[i]);
            max = std::max(max, last);
        }
        return max;
    }
};

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月22日上午9:58

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [0] * len(nums)
        dp[0] = nums[0]
        res = dp[0]

        for i in range(1, len(nums)):
            dp[i] = max(nums[i], dp[i - 1] + nums[i])
            res = max(dp[i], res)

        return res

时间复杂度: O(n)

0 赞同 0 条回复

花老爷普通 2023年7月21日上午11:34

滑动窗口，当到达索引i时，sum表示i之前数组的和，若为负数，则舍弃，sum=0，若为正数，则有加成应加上。
时间：O(n)
空间：O(1)

class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE, sum = 0;
        for (int num : nums) {
            sum += num;
            max = Math.max(max, sum);
            if (sum < 0)
                sum = 0;
        }
        return max;
    }
}

动态规划
时间：O(n)
空间：O(1)

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

0 赞同 0 条回复

怀瑾永久会员 2023年7月20日上午8:35
C++实现
int maxSubArray(std::vector& nums) {
int maxSum = nums[0];
int currentSum = nums[0];
```
for (int i = 1; i < nums.size(); ++i) {
    currentSum = std::max(nums[i], currentSum + nums[i]);
    maxSum = std::max(maxSum, currentSum);
}

return maxSum;
```
}

“`
0 赞同 0 条回复

登录以回复

局外人普通 2023年7月19日下午8:29

思想：动态规划
时间复杂度：O(n) 空间复杂度：O(1)

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

0 赞同 0 条回复

WhyNot 普通 2023年7月19日下午3:25

int maxSubArray(int* nums, int numsSize){
 int*dp=(int*)malloc(sizeof(int)*numsSize);
 dp[0]=nums[0];
 int max=nums[0];
 for(int i=1;i<numsSize;i++)
 {
     dp[i]=Max(dp[i-1]+nums[i],nums[i]);
     max=Max(max,dp[i]);
 }
 return max;
}
int Max(int a,int b)
{
    return a>b?a:b;
}

时间复杂度是O(n)，
空间复杂度是O(n)

0 赞同 0 条回复

Vow the vow。普通 2023年7月18日上午11:26

public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];  // 以num[i] 结尾的连续子数组
        dp[0] = nums[0];
        int res = dp[0];
        for(int i = 1; i < n; i++){
            dp[i] = nums[i] + (dp[i-1] < 0 ? 0 : dp[i-1]);
            res = Math.max(res,dp[i]);
        }
        return res;
    }

0 赞同 0 条回复

Jerry 普通 2023年7月17日下午11:07

// DP
class Solution {

    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];

        if (nums.length == 0) return 0;

        // base case
        dp[0] = nums[0];

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

        return getMaxSequence(dp); // 获取最大的值
    }

    private int getMaxSequence(int[] nums) {
        return Arrays.stream(nums).max().orElse(0);
    }

}

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

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月17日下午10:36

class Solution {
//时间O(n)，空间O(n)
    public int maxSubArray(int[] nums) {
        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 = dp[0];
        for(int i = 1;i < dp.length;i++){
            if(dp[i] > max){
                max = dp[i];
            }
        }

        return max;
    }
}

0 赞同 0 条回复

Ming 普通 2023年7月17日下午7:41

class Solution {
    public int maxSubArray(int[] nums) {
    int currentSum = nums[0];  // 当前子数组的和
    int maxSum = nums[0];      // 最大子数组和

    for (int i = 1; i < nums.length; i++) {
        // 对于当前元素，判断加入当前子数组后的和是否大于当前元素本身，
        // 如果是，则扩展当前子数组；如果不是，则重新开始一个新的子数组。
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        // 更新最大子数组和
        maxSum = Math.max(maxSum, currentSum);
    }
        return maxSum;
    }
}

0 赞同 0 条回复

小吕普通 2023年7月17日下午3:09

c++动态规划
int maxSubArray(vector& nums) {
int dp;
dp=nums[0];
int maxn =dp;
for(int i = 1;i<nums.size();i++)
{
dp =max((dp+nums[i]),nums[i]);
maxn = max(maxn,dp);
}
return maxn;
}

0 赞同 0 条回复

登录以回复

yxy 普通 2023年7月17日下午12:58

时间复杂度O(n)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        int prev = 0, cur = 0;
        int res = nums[0];
        for(int i=0;i<nums.size();i++)
        {
            cur=max(nums[i], prev+nums[i]);
            res = max(res, cur);
            prev = cur;
        }            
        return res;
    }
};

0 赞同 0 条回复

Yodl. 普通 2023年7月17日下午12:04

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

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

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

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

共以下 17 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复