LeetCode Best Time to Buy and Sell Stock II: Greedy and Proof

Overview

The greedy algorithm to add all the possible profit (increasing prices) and the proof are given to solve LeetCode Best Time to Buy and Sell Stock II.

LeetCode Best Time to Buy and Sell Stock II

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

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution Analysis: Greedy and Proof

This problem actually is quite simple, to get the maximum profit and since we are allowed to do as many transactions as we want, we just gather every possible profit and add them together. And the profit occurs at every increasing interval. So we just find all the increasing interval (non-overlap) among the set of prices and add the profit in each interval together, which results in the global maximum profits we need.

One (as for myself) might doubt this algorithm and let me convince you that it is indeed correct: let’s consider the following prices array:

……., b…c, d…f, …..

b…c and d…f are two increasing interval, but they are not continuous meaning that it breaks at c and d so, actually c > d. Our algorithm will give the sum:  (c – b) + (f – d) as the maximum profit, but one might argue that it could be b is very small and f is very large, is it possible to buy stock at b and sell it at f issue a larger profit? The answer it NO, because

{ (c – b) + (f – d) } – (f – b) = c – d > 0 => { (c – b) + (f – d) } > f – b

The above formula basically is saying that, we just add every NON-OVERLAP increasing interval will lead to the optimal profit. The above formula is also the basis of our algorithm! Our algorithm could also be considered as greedy and the time complexity is O(N).

The following code implements this idea in a simply way by directly translating. The code is accepted by LeetCode Best Time to Buy and Sell Stock II:

class Solution {
    public:
        // (1) greedy: naive implementation by finding every increasing interval
        int maxProfit(vector<int> &prices) {
            int ret = 0;
            int n = prices.size();
            int i = 0, j = 0;
            
            while (1) {
                if (j >= n) break;
                ++j;
                while (j < n && prices[j] > prices[j - 1]) 
                    ++j;
                ret += prices[j - 1] - prices[i];
                i = j;
            }
            return ret;
        }
};

While the above code is a bit tedious, one could find it could be simplified by adding even smaller piece profit because prices[j] – prices[i] = (prices[j] – prices[j-1]) + (prices[j - 1] – prices[j - 2]) + … + (prices[i+1] – prices[i]). This help get the following simple 4 lines of code which passes the OJ for LeetCode Best Time to Buy and Sell Stock II too:

int maxProfit(vector<int> &prices) {
            int ret = 0;
            for (int i = prices.size() - 1; i > 0; --i) 
                ret += max(prices[i] - prices[i-1], 0);
            return ret;
        }

Extension To LeetCode Best Time to Buy and Sell Stock II

There is more complicated similar problem which require some additional fees for buying and selling the stock, given such additional fees, the problem become more difficult, and we might use DP to solve it. For now the exact problem is not confirmed, so I don’t put too much effort here and I will post another one to discuss it when I find the exact problem.

(To be continued)

Summary

The greedy algorithm to add all the possible profit (increasing prices) and the proof are given to solve LeetCode Best Time to Buy and Sell Stock II.

Written on January 24, 2013