企业官网建设流程全解析

题目描述

给你一个整数数组pricespricesprices，其中prices[i]prices[i]prices[i]表示某支股票第iii天的价格

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。然而，你可以在 同一天 多次买卖该股票，但要确保你持有的股票不超过一股

返回你能获得的最大利润

示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。最大总利润为 4 + 3 = 7

示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。最大总利润为 4

算法思想

以折线图来查看股票价格：

通过这个图我们可以发现，只要将每一段递增区间中，最后一个值和第一个值和的差计算出来并求和就可以得到结果。那这就是贪心的思路，实现方式有两种，双指针和一天一天计算利润

双指针
设定两个指针i=0i = 0i=0，j=ij = ij=i

当prices[j+1]>prices[j]prices[j + 1] > prices[j]prices[j+1]>prices[j]时，jjj向后移动，否则jjj不动，最终jjj会移动至递增区间的最后一个值，此时计算prices[j]−prices[i]prices[j] - prices[i]prices[j]−prices[i]，加入结果

计算完成，让iii移动至j+1j + 1j+1的位置，继续找递增区间

一天天计算利润
递增区间最后一天减去第一天得到的利润，可以拆分成内部每一天减去前一天的利润之和。所以设定一个指针iii遍历数组，当prices[i+1]>prices[i]prices[i + 1] > prices[i]prices[i+1]>prices[i]时，计算它们的差，加到结果中

代码

// 1. 双指针classSolution{public:intmaxProfit(vector<int>&prices){intret=0;for(inti=0;i<prices.size();){intj=i;while(j<prices.size()-1&&prices[j+1]>prices[j]){j++;}ret+=prices[j]-prices[i];i=j+1;}returnret;}};// 2. 一天一天算利润classSolution{public:intmaxProfit(vector<int>&prices){intret=0;for(inti=0;i<prices.size()-1;++i){if(prices[i+1]>prices[i]){ret+=prices[i+1]-prices[i];}}returnret;}};