神刀安全网

Greedy Algorithm Example – 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).

This is aGreedy Algorithm puzzle from: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

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

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.

Greedy Algorithm Example – What is the Best Time to Buy and Sell Stock?

greedy-method

–EOF–

GD Star Rating

loading…

557 words

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Greedy Algorithm Example – What is the Best Time to Buy and Sell Stock?

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
分享按钮