Best Time to Buy and Sell Stock II

Problem: Best Time to Buy and Sell Stock III

The general idea is for each day k, we find out max profit by single transaction before k (including k) and max profit by single transaction after k (including k). Then we add these two results together to get an array of results at different days. Maximum of them is our answer. By including k, we mean sell at day k and buy at day k, which means we do nothing at day k and only do one transaction for the period.

Code in Python:

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) <= 1: return 0
        min_buy, dp_l2r = prices[0], [0]
        for i in xrange(1, len(prices)):
            if prices[i] <= min_buy:
                min_buy = prices[i]
                dp_l2r.append(dp_l2r[-1])
            else:
                dp_l2r.append(max(dp_l2r[-1], prices[i]-min_buy))
        max_sell, dp_r2l = prices[-1], [0] * len(prices)
        for i in xrange(len(prices)-2, -1, -1):
            if prices[i] >= max_sell:
                max_sell = prices[i]
                dp_r2l[i] = dp_r2l[i+1]
            else:
                dp_r2l[i] = max(dp_r2l[i+1], max_sell-prices[i])
        dp = [dp_l2r[i]+dp_r2l[i] for i in xrange(len(prices))]
        return max(dp)