LeetCode122. 买卖股票的最佳时机 II
题目
分析
利润产生在低价买入，高价卖出中。所以递减序列是没有利润的。为了利润最大，我们要找局部最低点和局部最高点，注意是局部，而不是全局 如[7,1,5,3,6,4]，选择1，5和3，6而不是直接从1到6。
所以贪心的局部最优就是 局部最小值和局部最大值的差值
这种思想有些像 LeetCode376. 摆动序列
代码
1 class Solution { 2 public: 3 int maxProfit(vector<int>& prices) { 4 int sum = 0; 5 if(prices.size() == 1) return 0; 6 for(int i =0;i < prices.size();i++){ 7 if(i< prices.size() -1 && prices[i] < prices[i+1]){ //注意边界 8 int j =i+1; 9 while(j < prices.size()-1 && prices[j] < prices[j+1]){ /注意边界 10 j++; 11 } 12 sum += prices[j] - prices[i]; 13 i = j; 14 } 15 } 16 return sum; 17 } 18 };
注意边界条件！注意边界条件！注意边界条件！比较到倒数第二个
分析（代码随想录Carl大佬思路）
将利润进行分解，把利润分解为每天的利润，如不是一段时间的利润。 假如第0天买入，第3天卖出，那么利润为：prices[3] - prices[0]。相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。有些类似差分。
代码
1 class Solution { 2 public: 3 int maxProfit(vector<int>& prices) { 4 int sum = 0; 5 if(prices.size() == 1) return 0; 6 for(int i =1;i < prices.size();i++){ 7 sum += max(prices[i] - prices[i-1],0); 8 } 9 return sum; 10 } 11 };