dede程序网站如何查看百度蜘蛛,竞价账户托管的公司有哪些,广府网站建设,最专业的营销网站建设公司排名链接#xff1a;力扣#xff1a;LCR 161. 连续天数的最高销售额
题目#xff1a;
某公司每日销售额记于整数数组 sales#xff0c;请返回所有 连续 一或多天销售额总和的最大值。
要求实现时间复杂度为 O(n) 的算法。 示例 1: 输入#xff1a;sales [-2,1,-3,4,-1,2,1…链接力扣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(vectorint sales) {int nsales.size();int cur0,ans-1e9;for(int i0;in;i){cursales[i];ansmax(ans,cur);if(cur0){cur0;}}return ans;}
};
动态规划代码
class Solution {
public:int maxSales(vectorint sales) {int nsales.size();int ans-1e9;vectorint v(n5);for(int i0;in;i){v[i1]max(sales[i1],v[i]sales[i1]);ansmax(ans,v[i]);}return ans;}
};
