首页 > 代码库 > 122. Best Time to Buy and Sell Stock II

122. Best Time to Buy and Sell Stock II

  不定期更新leetcode解题java答案。

  采用pick one的方式选择。

  由于随机到了系列问题,在此继续做后序版本。

  题意为给定一个数组,数组分别表示当天物品的售价,允许多次买卖(卖的前提是买,买的前提是卖,也就是身上没有物品时才可以买),问最大的收益是多少。

  首先的分析方式就是,我们应该在什么时候买,在什么时候卖。

  试想,当我们购买了物品,隔天如果涨价了,我们不卖,要看第三天的价格是不是比第二天低;如果降价了,那么我们应该在第二天买,再进行判断。这个步骤可以换成逻辑为:

  我们今天购买了物品,第二天涨价了,需要进行第三天的判断;如果降价了,那么我们应该在前一天卖掉,在第二天买进(同上段,如果刚买入第二天就降价,那么就在买入当天卖掉,也就等同于第一天不买入)。由上述分析可得如下代码:

 1 public class Solution {
 2     public int maxProfit(int[] prices) {
 3         if(prices.length == 0)
 4             return 0;
 5 
 6         int profit = 0, buyPrice = prices[0];
 7         
 8         for(int i = 1; i < prices.length; i++){
 9             if(prices[i] < prices[i - 1]){
10                 profit += prices[i - 1] - buyPrice;
11                 buyPrice = prices[i];
12             }
13         }
14         //由于循环的最后有可能没有执行卖出的操作
15         profit += prices[prices.length - 1] - buyPrice;
16         
17         return profit;
18     }
19 }

  同样的,python代码如下:

 1 class Solution(object):
 2     def maxProfit(self, prices):
 3         """
 4         :type prices: List[int]
 5         :rtype: int
 6         """
 7         if len(prices) == 0:
 8             return 0;
 9         profit = 0
10         buyPrice = prices[0]
11         lastPrice = prices[0]
12         
13         for price in prices:
14             if lastPrice > price:
15                 profit += lastPrice - buyPrice
16                 buyPrice = price
17                 
18             lastPrice = price
19         
20         profit += prices[len(prices) - 1] - buyPrice
21         
22         return profit

 

  当然,我们可以换一种思考的方式,利用贪心法,只要第二天比第一天的价格高,那么我们就在今天买,第二天卖出,获取局部最优解,以达到最终最大收益。这种想法由于没有前文的多天卖出的判定条件(第三天比第二天低),循环后不需要再补充代码,具体代码如下:

 1 public class Solution {
 2     public int maxProfit(int[] prices) {
 3         int profit = 0;
 4         
 5         for(int i = 1; i < prices.length; i++)
 6             if(prices[i] > prices[i - 1])
 7                 profit += prices[i] - prices[i - 1];
 8 
 9         return profit;
10     }
11 }

  对应python代码如下:

 1 class Solution(object):
 2     def maxProfit(self, prices):
 3         """
 4         :type prices: List[int]
 5         :rtype: int
 6         """
 7         if len(prices) == 0:
 8            return 0
 9         lastPrice = prices[0]
10         profit = 0
11         for price in prices:
12             if price > lastPrice:
13                 profit += price - lastPrice
14             lastPrice = price
15         return profit

 

122. Best Time to Buy and Sell Stock II