# Share my O(n) C++ solution with proof and explanation

• ## 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:

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

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

## 4.1.1 Time Complexity Analysis of Plan A:

#### 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.3 Improvement

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

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

Which means,

## 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:

So,

Which means:

## 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.

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

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

We need to confirm the final answer

## 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;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.