# [Classic, Buy-And-Sell-Stock]
# https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
# 123. Best Time to Buy and Sell Stock III

# History:
# 1.
# Aug 25, 2019
# 2.
# Nov 23, 2019
# 3.
# May 5, 2020

# https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/discuss/149383/Easy-DP-solution-using-state-machine-O(n)-time-complexity-O(1)-space-complexity

# 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 at most
# two transactions.
#
# Note: You may not engage in multiple transactions at the same time (i.e.,
# you must sell the stock before you buy again).
#
# Example 1:
#
# Input: [3,3,5,0,0,3,1,4]
# Output: 6
# Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3),
# profit = 3-0 = 3.
#              Then buy on day 7 (price = 1) and sell on day 8 (price = 4),
#              profit = 4-1 = 3.
# Example 2:
#
# Input: [1,2,3,4,5]
# Output: 4
# Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5),
# profit = 5-1 = 4.
#              Note that you cannot buy on day 1, buy on day 2 and sell them
#              later, as you are
#              engaging multiple transactions at the same time. You must
#              sell before buying again.
# Example 3:
#
# Input: [7,6,4,3,1]
# Output: 0
# Explanation: In this case, no transaction is done, i.e. max profit = 0.


class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices:
            return 0
        buy1_state = buy2_state = sell1_state = sell2_state = float('-inf')

        for p in prices:
            buy1_state = max(buy1_state, -p)
            sell1_state = max(sell1_state, buy1_state + p)
            buy2_state = max(buy2_state, sell1_state - p)
            sell2_state = max(sell2_state, buy2_state + p)

        return sell2_state
