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

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

要求：

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

shuaidi

更新于 3 年前 236 14

共以下 14 个回答

kfaebot 普通 2024年5月10日下午9:58

class Solution {
public:
    int maxSales(vector<int>& sales) {
        //明确数组含义dp[i]表示末尾元素为sales[i]的最大子序列和
        vector<int> dp(sales.size());
        //初始化
        dp[0]=sales[0];
        //表达式
        int max_res=dp[0];
        for(int i=1;i<sales.size();i++){
            dp[i]=max(dp[i-1]+sales[i],sales[i]);
            if(max_res<dp[i]){
                max_res=dp[i];
            }
        }
        return max_res;
    }
};

0 赞同 0 条回复

=.= 普通 2024年4月12日下午10:54

class Solution {
public int maxSales(int[] sales) {
int n = sales.length;

    int[] dp = new int[n];
    int ans = sales[0];
    dp[0] = sales[0];
    for(int i=1; i<n; i++){
        dp[i] = Math.max(sales[i], sales[i]+dp[i-1]);
        ans = Math.max(ans, dp[i]);
    }

    return ans;
}

}

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

0 赞同 0 条回复

南梁陈庆之普通 2024年4月8日下午11:11

动态规划解决，时间复杂度O（N），空间复杂度O（N）

class Solution {
    public int maxSales(int[] sales) {
        int n = sales.length;
        int[] dp = new int[n + 1];
        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            dp[i] = Math.max(dp[i - 1] + sales[i - 1], sales[i - 1]);
            max = Math.max(max, dp[i]);
        }


        return max;
    }
}

0 赞同 0 条回复

神经蛙普通 2024年4月2日下午11:02

class Solution {
public:
int maxSales(vector& sales) {
int pre = 0, maxAns = sales[0];
for (const auto &x: sales) {
pre = max(pre + x, x);
maxAns = max(maxAns, pre);
}
return maxAns;
}
};
打卡

0 赞同 0 条回复

登录以回复

白雪公主倒拔垂杨柳永久会员 2024年4月2日下午8:29

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(dp[i-1]+sales[i],sales[i]);
            max=Math.max(dp[i],max);
        }
        return max;
    }
}

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

0 赞同 0 条回复

一个达不刘普通 2024年4月1日上午11:25
class Solution {
public:
int maxSales(vector& sales) {
//dp[i]为包含sales[i]的最大利润
int n = sales.size();
int res = sales[0];
for(int i=1;i<n;i++){
if(sales[i-1]>0) sales[i] += sales[i-1];
if(sales[i] > res) res = sales[i];
```
    }
    return res;
}
```
};
0 赞同 0 条回复

登录以回复

王位詮釋普通 2024年3月31日下午4:35

帅地优化之后的版本：
class Solution {
    public int maxSales(int[] sales) {
        //dp代表到第i天（包括i）为止最大的连续天数销售额
        int dp = sales[0];
        int max = sales[0];//表示最后返回的最大的连续天数销售额
        for(int i = 1;i<sales.length;i++){
            dp = Math.max(sales[i],sales[i]+dp);
            max = Math.max(max,dp);
        }
        return max;
    }
}
自己写的：
class Solution {
    public int maxSales(int[] sales) {
        //定义：dp[i]表示截止到第i天之前，第i天的最大销售额
        int[] dp = new int[sales.length];
        dp[0] = sales[0];
        int max = sales[0];
        for(int i =  1;i<sales.length;i++){
            if(dp[i-1]<0){
                dp[i] = sales[i];
            }else{
                dp[i] = dp[i-1]+sales[i];
            }
            if(max<dp[i]){ 
                max = dp[i];
            }
        }
        return max;
    }
}

0 赞同 0 条回复

heathhou 普通 2024年3月31日上午10:07

class Solution {
public:
    int maxSales(vector<int>& sales) {
        int len = sales.size();
        // dp[i]: 第i天，销售额总和的最大值
        vector<int> dp(len, 0);
        // 关系式：dp[i] = max(dp[i-1] + sales[i], sales[i])

        // 初始化
        dp[0] = sales[0];
        // 通过关系式来计算出 dp[n]
        for(int i = 1; i < len; ++i){
            dp[i] = max(dp[i-1] + sales[i], sales[i]);
        }
        sort(dp.begin(), dp.end());
        return dp[len - 1];
    }
};

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

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月31日上午9:26

打卡

class Solution {
public:
    int maxSales(vector<int>& sales) {
        int sum = 0, _max = INT32_MIN;
        for(int& x : sales) {
            sum += x;
            _max = max(_max, sum);
            if(sum < 0) sum = 0;
        }
        return _max;
    }
};

0 赞同 0 条回复

方铎码农普通 2024年3月30日下午9:29

//动态规划的方法，连续盈利的最大天数和利润值自然最大，dp[i] = dp[i-1] + sales[i](dp[i-1] > 0) sales[i](dp[i-1]<0)
class Solution {
    public int maxSales(int[] sales) {
        int res = sales[0];
        for (int i = 1; i < sales.length; i++) {
            sales[i] += Math.max(sales[i-1],0);
            res = Math.max(res,sales[i]);
        }
        return res;
    }
}

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

0 赞同 0 条回复

Raphtalia. 普通 2024年3月30日下午5:11

class Solution {
public:
int maxSales(vector& sales) {
int n = sales.size();
int res = sales[0];
int dp = sales[0];
for(int i = 1; i < n; i ++) {
dp = max(dp + sales[i], sales[i]);
res = max(res, dp);
}
return res;
}
};
时间复杂度O（n),空间复杂度o(1)

0 赞同 0 条回复

登录以回复
紫芝普通 2024年3月30日下午4:09

时间复杂度：O(n)

“`c++
class Solution {
public:
int maxSales(vector& sales) {
int maxi = sales[0];
int cur = maxi;
for (int i=1; i maxi ? cur : maxi;
}
return maxi;
}
};
“`

0 赞同 0 条回复

登录以回复

云无深雁影普通 2024年3月29日下午11:30

class Solution {
public int maxSales(int[] sales) {

    int max[] = new int[sales.length];
    int ans = -101;
    max[0] = sales[0];
    for(int i = 1; i < sales.length; i++){
        max[i] = Math.max(sales[i],max[i-1] + sales[i]);

    }
    for(int i = 0; i < sales.length;i++)
        ans = Math.max(ans,max[i]);

    return ans;
}

}
//时空复杂度均为ON

0 赞同 0 条回复

机电皮怪永久会员 2024年3月29日下午11:27
时间复杂度O(N),空间复杂度O(1)

“`C++
class Solution {
public:
int maxSales(vector& sales) {
if(sales.empty() == true)
{
return {};
}
int days = sales.size();
int max1 = sales[0];
int dp = sales[0];
//边缘条件
```
    for(int i = 1; i < days; i++)
    {
        dp = max(dp + sales[i], sales[i]);
        max1 = max(dp, max1);
    }
    return max1;
}
```
};

“`
0 赞同 0 条回复

登录以回复

# 回答此问题取消回复

后才能回答

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

共以下 14 个回答

# 回答此问题 取消回复

# 回答此问题取消回复