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
网友评论