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.

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.

```
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]).