买卖股票的最佳时机（二）

LeetCode算法网站算法题

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

1.暴力解法——枚举出所有可能，再比较最大收益，Digui函数是计算从idx往后的最大收益

class Solution { private: int Digui(vector<int>&pri,int idx) { if(idx>pri.size()-1) return 0; int max=0; for(int buy=idx; buy<pri.size()-1; buy++)//枚举从idx往后第几天第一次买入股票 { int maxprofit=0; for(int sell=buy+1; sell<pri.size(); sell++)//枚举卖出股票的日子 { if(pri[sell]>pri[buy]) { proift=Digui(pri,sell+1)+pri[sell]-pri[buy];//卖完之后的最大收益 if(profit>maxprofit) { maxprofit=profit; } } } if(maxprofit>max)//获取最大收益 { max=maxprofit; } } return max; } public: int maxProfit(vector<int>& prices) { return Digui(prices,0); } };

2.峰谷法

我们在一个波谷中买入一个股票之后，再遇到一个波峰，但是不卖，则会亏损；

我们在一个波峰中卖出一个股票之后，再遇到一个波谷，但是不买，则会亏损。

所以所有的波谷和波峰对都需要进行买卖的操作。

class Solution { public: int maxProfit(vector<int>& prices) { int i; int top=prices[0],low=prices[0]; int profit=0; while(i<prices.size()-1) { while(i<prices.size()-1&&prices[i]>=prices[i+1]) i++; low=prices[i]; while(i<prices.size()-1&&prices[i]<=prices[i+1]) i++; top=prices[i]; profit+=top-low; } return profit; } };

3.简单的一次遍历，这里有一个要点理解就是，有可能在一天之中刚刚卖完股票，又买入股票

class Solution { public: int maxProfit(vector<int>& prices) { int pro; for(int i=1;i<prices.size();i++){ if(prices[i]>prices[i-1]){ pro+=prices[i]-prices[i-1]; } } return pro; } };