## 1. Problem

a. You have an array.

b. The ith element in the array is the price of a given stock on day i.

c. You are only permitted to complete at most one transaction.

d. Design an algorithm to find the MAXIMUM profit.

## 2. Implications

a. The smaller i means the price on an earlier day i.

b. If you complete one transaction, you must buy a stock before you sell it.

## 3. Abstraction and generalization

a. Assume that the array is a sequence of size n.

p(1), p(2), p(3), p(4),..., p(n), n > 1

b. Suppose the the maximum price after day k is:

m(k) = max{p(k + 1), p(k + 2),..., p(n)}, 1 ≤ k < n, k ∈ Z

c. The maximum profit for buying stock on day k is:

f(k) = m(k) - p(k), 1 ≤ k < n, k ∈ Z

d. We need to find out:

max{f(k)}, 1 ≤ k < n, k ∈ Z

## 4. Algorithms

## 4.1 Plan A (start-to-end approach)

a. Calculates f(1), f(2), f(3),..., f(n - 1) one by one

b. Find the answer max{f(k)}

## 4.1.1 Time Complexity Analysis of Plan A:

f(1) = m(1) - p(1) = max{p(2), p(3),..., p(n)} - p(1) (n - 1 visits, 1 minus)

f(2) = m(2) - p(2) = max{p(3), p(4),..., p(n)} - p(2) (n - 2 visits, 1 minus)

.......

f(n - 1) = m(n - 1) - p(n - 1) = max{p(n)} - p(n - 1) (1 visits, 1 minus)

The total visits and minus is

2 + 3 +... + n - 1 + n = (n + 2)(n - 1)/2 = O(n^2).

**This is an O(n^2) algorithm. How can we decrease the time complexity?**

## 4.1.2 Disadvantage of Plan A

m(k) = max{p(k+1), p(k+2),..., p(n)} is recalculated NEWLY for EVERY k.

## 4.1.3 Improvement

a. Make former m(k) useful for calculating a new m(k)

b. Find out a recursion formula for m(k).

## 4.2 Plan B (end-to-start approach)

## 4.2.1 Recursion Formula

m(k) = p(n), k = n - 1

m(k - 1) = max{p(k), m(k)}, 2 ≤ k < n, k ∈ Z

Which means,

m(n - 1) = p(n)

m(k - 1) = p(k), if p(k) > m(k)

m(k - 1) = m(k), else

## 4.2.2 Proof

When k = n - 1, the only one day after k is n, so

m(n - 1) = p(n)

If m(k) = p(t), means:

p(t) ≥ p(k+1), p(k+2),..., p(n), t ∈ [k + 1, n]

When calculating m(k - 1), we want to find a p(t') that:

p(t') ≥ p(k), p(k+1), p(k+2),..., p(n), t' ∈ [k, n]

So,

p(t') ≥ p(k), p(t') ≥ p(t)

Which means:

m(k - 1) = max{p(k), m(k)}

## 4.2.3 Time Complexity Analysis of Plan B:

Since we calculate m(k - 1) based on m(k), this is an end-to-start approach.

We calculate f(k) from k = n - 1 to k = 1.

f(n - 1) = m(n - 1) - p(n - 1) = p(n) - p(n - 1) (0 compare, 1 minus)

f(n - 2) = m(n - 2) - p(n - 2) = max{p(n - 1), m(n - 1)} - p(n - 2) (1 compare, 1 minus)

.......

f(2) = m(2) - p(2) = max{p(3), m(3)} - p(2) (1 compare, 1 minus)

f(1) = m(1) - p(1) = max{p(2), m(2)} - p(1) (1 compare, 1 minus)

#### The total compare and minus is

1 + 2 + ... + 2 + 2 = 1 + 2(n - 2) = 2n - 3 = O(n)

**This is a much better O(n) algorithm, which is the solution.**

## 5. Answer

We need to confirm the final answer

If max{f(k)} ≥ 0 (1 ≤ k < n, k ∈ Z), complete just one transaction, the answer is max{f(k)}.

If max{f(k)} < 0 (1 ≤ k < n, k ∈ Z), don't complete any transaction, the answer is 0.

## 6. Code

```
class Solution {
public:
int maxProfit(vector<int>& prices) {
int maxSell = 0;
int maxProfit = 0;
for(int i = prices.size() - 1; i > 0; i--)
{
if(prices[i] > maxSell)
{
maxSell = prices[i];
}
if(maxSell - prices[i - 1] > maxProfit)
{
maxProfit = maxSell - prices[i - 1];
}
}
return maxProfit;
}
};
```