美文网首页
Buy Stock III

Buy Stock III

作者: GakkiLove | 来源:发表于2018-05-27 02:55 被阅读0次

    Given an array of positive integers representing a stock’s price on each day. On each day you can only make one operation: either buy or sell one unit of stock, at any time you can only hold at most one unit of stock, and you can make at most 2 transactions in total. Determine the maximum profit you can make.

    Assumptions

    The give array is not null and is length of at least 2

    Examples

    {2, 3, 2, 1, 4, 5, 2, 11}, the maximum profit you can make is (5 - 1) + (11 - 2) = 13

    class Solution(object):
      def maxProfit(self, array):
        if not array:
          return 0
        profits = []
        max_profit = 0
        current_min = array[0]
        for price in array:
          current_min = min(current_min,price)
          max_profit = max(max_profit,price - current_min)
          profits.append(max_profit)
        total_max = 0
        max_profit = 0
        current_max = array[-1]
        for i in range(len(array) - 1,-1,-1):
          current_max = max(current_max,array[i])
          max_profit = max(max_profit,current_max - array[i])
          total_max = max(total_max,max_profit + profits[i])
        return total_max
    

    相关文章

      网友评论

          本文标题:Buy Stock III

          本文链接:https://www.haomeiwen.com/subject/fpgvjftx.html