力扣:LCR 161. 连续天数的最高销售额(最大子数组和,动态规划入门)

发布时间:2023年12月22日

链接:力扣:LCR 161. 连续天数的最高销售额

题目:

某公司每日销售额记于整数数组?sales,请返回所有?连续?一或多天销售额总和的最大值。

要求实现时间复杂度为?O(n)?的算法。

示例 1:

输入:sales = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:[4,-1,2,1] 此连续四天的销售总额最高,为 6。

示例 2:

输入:sales = [5,4,-1,7,8]
输出:23
解释:[5,4,-1,7,8] 此连续五天的销售总额最高,为 23。?

提示:

  • 1 <=?arr.length <= 10^5
  • -100 <= arr[i] <= 100

解法:

最大子数组和思路:很明显,这题可以使用求最大子数组和(子数组就是数组中的一个连续部分)的思路来做,首先我们要初始化答案,因为有可能出现负数,所以我们要将其设置为一个很小的负数。接着我们要对? ?sales 数组进行遍历,用 cur 来记录连续的销售额,每次记录都对 ans 和 cur 取其最大值。如果? ?cur < 0, 不妨置零重新开始,因为再加上一个正数销售额也不会比单个正数高。遍历结束最终的? ?ans 就是我们的答案。

动态规划思路:

?做题步骤:

1.重述问题:求有连续?一或多天销售额总和的最大值。

2.找到最后一步:以这个数作为子数组的最后一个元素。

3.去掉最后一步:以这个数前一个数作为子数组的最后一个元素。

4.边界:无需考虑

分析:

从下标0开始遍历sales数组,因为是连续的,所以只要跟子问题(上一个元素)加上当前销售额的和销售额的最大值,再对所有 v 元素进行取最大值即可。

最大子数组和的代码:

class Solution {
public:
    int maxSales(vector<int>& sales) {
        int n=sales.size();
        int cur=0,ans=-1e9;
        for(int i=0;i<n;i++){
            cur+=sales[i];
            ans=max(ans,cur);
            if(cur<0){
                cur=0;
            }
        }
        return ans;
    }
};

动态规划代码:

class Solution {
public:
    int maxSales(vector<int>& sales) {
        int n=sales.size();
        int ans=-1e9;
        vector<int> v(n+5);
        for(int i=0;i<n;i++){
            v[i+1]=max(sales[i+1],v[i]+sales[i+1]);
            ans=max(ans,v[i]);
        }
        return ans;
    }
};

文章来源:https://blog.csdn.net/m0_73680520/article/details/135101543
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。