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


  • 2
    K

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


Log in to reply
 

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