Greedy Algorithm: What is the 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.

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

Greedy Algorithm to Determine Best Time to Buy and Sell Stock

Greedy Algorithm is often easy to implement however to it is usually not so straightforward to come up with this idea and sometimes even hard to prove it is correct. There are constraints in the description that makes a Greedy Algorithm suitable for solving this puzzle.

The Greedy approach always picks the optimal (better) solution at each iteration based on the current situation. For example, in this case, every day you can choose selling or not selling the stock. The greedy algorithm always choose a strategy that does not lose profit.

So, for example, the inputs are 1, 2 and 4. So the strategy goes like this: The first day you buy at price 1, the second day you sell at price 2 so you have profit 1. And you buy at price 2, the third day you sell at price 4 so you have another profit 2. The total profit is 3. Of course, if the price at day 3 is 1, so you choose not selling the stock because it will make you lose profit.

The Greedy solution works in this case because (1) you can’t go back to previous days when you decide to sell the stock at a higher price (2) The profit you have now does not affect the profits you make individual days later. In other words, if you can make more profits by today, the total profit you can get all together can be always increased by choosing a better strategy today.

1
2
3
4
5
6
7
8
9
10

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

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

The Greedy Algorithm can be described as follows, remember at each iteration, you always choose what is best (e.g. maximize your profit) for you at that point.

Time complexity for this greedy algorithm is O(N) – and space complexity is O(1).

greedy-method

Buy and Sell Stock Algorithms

• C/C++ Coding Exercise – Best Time to Buy and Sell Stock
• Greedy Algorithm Example – What is the Best Time to Buy and Sell Stock?
• Teaching Kids Programming – Best Time to Buy and Sell Stock (Buy and Sell Once – Three Algorithms)

–EOF (The Ultimate Computing & Technology Blog) —