AMAZING problem

#1

One of the best problems on this site.

Solved this correctly on LEETCODE…but it failed here…so optimized it…delivers immense satisfaction.

No wonder it is a favourite Interview question.

#2

can you please share your approach?

#3 
class Solution:
    # @param A : tuple of integers
    # @return an integer
    def maxProfit(self, A):
        if not A: return 0
        xmin = A[0]
        p = [0] * len(A)
        for i, x in enumerate(A):
            xmin = min(xmin, x)
            p[i] = max(p[i-1], x - xmin)
        profit = 0
        xmax = A[len(A)-1]
        for i in range(len(A)-1,-1,-1):
            xmax = max(xmax, A[i])
            profit = max(profit, p[i] + xmax - A[i])
        return profit

You can use the same idea from the “Stocks I” problem where profit(A[0…i]) is the profit obtained with only 1 transaction. The answer to this problem is max(profit(A[0…i]) + profit(A[i+1…n])). You can compute profit(A[i+1…n]) efficiently in a similar manner as profit(A[0…i]).