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