<filename>leetcode/hard/Best_Time_to_Buy_and_Sell_Stock_III.py
# -*- coding: utf-8 -*-

"""
created by huash at 2015-05-01 17:43

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 (ie, you must sell the stock before you buy again).

"""
__author__ = 'huash'

import sys
import os

class Solution:
    # @param {integer[]} prices
    # @return {integer}
    def maxProfit(self, prices):
        """
        p1, p2, p3, p4 分别表示操作1次，2次，3次，4次后的利润。
        2次操作完成一次交易。
        :param prices:
        :return:
        """
        if not prices:
            return 0

        p1 = -prices[0]
        p2 = 0
        p3 = -1000000
        p4 = 0

        for d in range(1, len(prices)):
            p4 = max(p4, p3+prices[d])
            p3 = max(p3, p2-prices[d])
            p2 = max(p2, p1+prices[d])
            p1 = max(p1, -prices[d])

        return max(0, p2, p4)

s = Solution()
print(s.maxProfit([1]))
print(s.maxProfit([1, 5, 3, 7]))
print(s.maxProfit([1, 3, 5]))
print(s.maxProfit([1, 5, 2, 3]))