121. Best Time to Buy and Sell Stock
题目的要求是只买卖一次,买的价格越低,卖的价格越高,肯定收益就越大
遍历整个数组,维护一个当前位置之前最低的买入价格,然后每次计算当前位置价格与之前最低价格的差值,获得最大差值即为结果
class Solution { public: int maxProfit(vector<int>& prices) { if(prices.empty()) return 0; int min_num = prices[0]; int profit = 0; for(int i = 1;i < prices.size();i++){ min_num = min(min_num,prices[i]); if(prices[i] > min_num) profit = max(profit,prices[i] - min_num); } return profit; } };
122.Best Time to Buy and Sell Stock II
可以买任意次,所以只要当前的价格比之前的一个多,就买卖,这样最多
class Solution { public: int maxProfit(vector<int>& prices) { int res = 0; for(int i = 1;i < prices.size();i++){ if(prices[i] > prices[i-1]) res += prices[i] - prices[i-1]; } return res; } };
309. Best Time to Buy and Sell Stock with Cooldown
https://www.cnblogs.com/grandyang/p/4997417.html
https://blog.csdn.net/qq508618087/article/details/51671504
注意题目的注释:you must sell the stock before you buy again,也就是说不能买了又买,卖了又卖,只能买一次再卖一次
用buy、sell两个数组表示当前位置以buy、sell操作结尾的最大收入,以buy为例,当前状态只可能来自两种情况:一、这一位置不做任何操作,就是不买也不卖 二、这一位置买,那之前的状态就是i-2的时候卖出了东西
初始化的时候注意0、1都要初始化,因为i-2,从2开始的循环。
class Solution { public: int maxProfit(vector<int>& prices) { int length = prices.size(); if(length <= 0) return 0; vector<int> buy(length+1,0); vector<int> sell(length+1,0); buy[1] = -prices[0]; for(int i = 2;i <= length;i++){ buy[i] = max(buy[i-1],sell[i-2] - prices[i-1]); sell[i] = max(sell[i-1],buy[i-1] + prices[i-1]); } return max(buy[length],sell[length]); } };
714. Best Time to Buy and Sell Stock with Transaction Fee
https://www.cnblogs.com/grandyang/p/7776979.html
class Solution { public: int maxProfit(vector<int>& prices, int fee) { vector<int> buy(prices.size(),0); vector<int> sell(prices.size(),0); buy[0] = -prices[0]; for(int i = 1;i < prices.size();i++){ buy[i] = max(buy[i-1],sell[i-1] - prices[i]); sell[i] = max(sell[i-1],buy[i-1] + prices[i] - fee); } return max(buy[prices.size() - 1],sell[prices.size() - 1]); } };