首页 > 代码库 > Best Time to Buy and Sell Stock II
Best Time to Buy and Sell Stock II
https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
解题思路：
和Best Time to Buy and Sell Stock问题相比，可以多次买卖。
一个比较tricky的解法，因为不限制买卖次数。只要第二天是涨价的，就可以立刻卖掉，然后再买，无需考虑到底第三天是不是也要涨价。因为1-2-3和1-3的赚的钱是一样的。
比较循规蹈矩的解法。比较前后两天的数值，只要是涨价的，就拿在手里，不卖。只要一降价，就证明前面一天要卖掉。同时假定降价这天买入，如此往复。
public class Solution { public int maxProfit(int[] prices) { int maxProfit = 0; for (int i = 0; i < prices.length;){ int j = i + 1; while(j < prices.length && prices[j] >= prices[j - 1]){ j++; } maxProfit += prices[j - 1] - prices[i]; i = j; } return maxProfit; }}
这是上面思路的一个实现，同样为O(n^2)，但因为i直接跳到j，实际接近于O(n)。
public class Solution { public int maxProfit(int[] prices) { int maxProfit = 0; int buy_price = 0; if(prices.length == 0){ return 0; }else{ buy_price = prices[0]; } for (int i = 1; i < prices.length;){ if(prices[i] < prices[i - 1]){ maxProfit += prices[i - 1] - buy_price; buy_price = prices[i]; } if(i == prices.length - 1 && prices[i] >= prices[i - 1]){ maxProfit += prices[i] - buy_price; } i++; } return maxProfit; }}
这是一个O(n)的实现。存入prices[i]作为买入值，在价格下跌的时候才更新，同时计算最大利润额。考虑一个特殊情况，最后一个区间是一直涨价的，所以这个情况只有判断i已经到最后，并且涨价来作为结束，否则将会漏掉这个区间的profit值。
同样，这个方法与上面的比不太清晰。
Best Time to Buy and Sell Stock II