LeetCode Best Time to Buy and Sell Stock: Dynamic Programming (DP)

Overview

Dynamic Programming (DP) is used to solve LeetCode Best Time to Buy and Sell Stock in O(N) time and O(1) space, the key is find the min/max price in O(1) time.

LeetCode Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Solution Analysis: Dynamic Programming (DP)

The naive try (brute force) way is to just scan through all prices and find the pair with the maximum difference, the time complexity is O(N^2). This yields the following code which would get Time Limit Exceeds error from LeetCode OJ for this Best Time to Buy and Sell Stock problem:

class Solution {
    public:
        // (1) brute force: TLE
        int maxProfit(vector<int> &prices) {
            int n = prices.size();
            if (n < 2) return 0;
            int ret = 0;
            for (int i = 0; i < n; ++i) {
                for (int j = i + 1; j < n; ++j) {
                    ret = max(ret, prices[j] - prices[i]);
                }
            }
            return ret;
        }
};

The problem with the above code is that there are lot of redundant computations wasted. The key point is that, from another angle, to find the maximum profit (maximum difference) for some date say i when you buy the stock is equivalent to finding the maximum prices in day i + 1 to the N-th day (don’t try to stick to the maximum difference, maximum difference could be misleading and keep you stuck in the O(N^2) comparisons). And remember maximum could be found in linear time right? This could motivate the following linear time algorithm: Start from the last day, linear scan through until the first day, while dealing with i-th day, just find the day in i+1 to N with maximum prices, and such day could be found in constant time if we use the previous maximum value among the days from i+2 to N.  The time complexity is O(N) as linear scan. And the following code implements this idea and is accepted by the LeetCode OJ to pass this Best Time to Buy and Sell Stock problem:

class Solution {
    public:
        int maxProfit(vector<int> &prices) {
            int max_price = -1;
            int max_profit = 0;
            for(int i = prices.size() - 1; i >= 0; --i) {
                max_price = max(max_price, prices[i]);
                max_profit = max(max_profit, max_price - prices[i]);
            }
            return max_profit;
        }
};

Similarly, if we start from the beginning of the price array, i.e., start from day 0 to day 1 to … day n, which is more natural, we could come up with a O(N) time solution by finding the minimum prices among prices[0…i] and for each day i, we can know the maximum profit we could earn by selling it at day i. And the final maximum profit would be the global maximum values among all the maximum profits at day i’s. The following code implements this too:

int maxProfit(vector<int> &prices) {
            int minPrices = INT_MAX;
            int ret = 0;

            int n = prices.size();
            for (int i = 0; i < n; ++i) {
                minPrices = min(minPrices, prices[i]);
                ret = max(ret, prices[i] - minPrices);
            }
            return ret;
        }

Remarks: Try different thinking from different angles. The linear scan is bit from dynamic programming ‘s angle.

Update: There is another approach by converting the problem into Maximum Subarray problem: LeetCode Maximum Subarray: 4 methods, DP, Divide and Conquer. That is, from the original array prices, we make a new array called A with A[i] = prices[i] – prices[i-1], then the answer to best time to buy and sell stock is the same answer the find the maximum sum of consecutive subarray in array A. The following code implements this idea.

class Solution {
    public:
        int maxProfit(vector<int> &prices) {

            int ret = 0; //
            int sum = 0; //
            int n = prices.size();

            for (int i = 1; i < n; ++i) {
                sum += prices[i] - prices[i-1];
                ret = max(ret, sum);
                sum = max(0, sum);
            }
            return ret;
        }

};

Summary

Dynamic Programming (DP) is used to solve LeetCode Best Time to Buy and Sell Stock in O(N) time and O(1) space, the key is find the min/max price in O(1) time.

Written on January 14, 2013