tsanmmmm2000's Tech Blog

Question

Say you have an array for which the i^th 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).

Thinking

仔細觀察其實可以發現此題存在著Greedy性質，因此可以用貪婪演算法(Greedy Algorithm)來快速求得答案，即每一次的計算都選擇現下最好的狀態，如此不斷地改進，從而讓最後的結果也是最好的。如下圖的情境之下，每次變化的加總(A+B+C)與實際總和(D)其實是一樣的

My C# Solution

public class Solution {
    public int MaxProfit(int[] prices) {
        var maxProfit = 0;
        for(var i = 1; i < prices.Length; i++)
        {
            if (prices[i] > prices[i-1])
            {
                maxProfit += prices[i] - prices[i-1];
            }
        }
        return maxProfit;
    }
}

Reference：演算法筆記- Greedy Method、Greedy Algorithm - Wikipedia