iT邦幫忙

DAY 4
0

連續30天,挑戰演算法系列 第 4

[Day04] 股市中最佳買賣時機-II

題目來源:Best Time to Buy and Sell Stock II

問題
這題是 股市中最佳買賣時機-I 的進階版,假設你有一個陣列,該陣列第 i 個元素代表第 i 天股票的價格,並且你 可以有多次買賣的機會 ,請設計一個演算法求得最大的力論為何?

例子

  1. 股市 = {3, 2, 6, 5, 0, 3},
    則最大利潤為 4 (第二天買進 第三天賣出)
  2. 股市 = { 2, 1 },
    則最大利潤為 0 (因為買了一定賠)
  3. { 1, 3, 6, 8, 9, 6, 4, 2, 1 },
    則最大利潤為 8

想法
這一題其實如果懂題目,其實還滿簡單的。其實就跟昨天的一樣,只是多了一個條件,除了他主要就是要你再該陣列中找出最大值最小值而已!只不過,因為股票是不能在 未來買 並且到 過去賣,因此這 最大/最小值 的差還多了一個限制就是,最大值的 index 必須大於 最小值的 index。所以,這樣下在整個題目就變的簡單很多了!
另外,因為這題可以 多次買賣,所以只要找到 前一個後一個 大,就可以進行買賣賺差價了!
因此,這題主要的重點就是要 累加 每一次買賣的利潤,在 股市中最佳買賣時機-I 這題因為要求最大,所以我們只儲存一個,但這一題可以多次買賣,所以我們只要將每一次買賣的的價差累加起來就是我們要的答案了。

解法
while 股市天數 <= 1 天
直接回傳 0
for 第一天 到 最後一天
if 今天價格 < 最小價格
最小價格就改成今天價格
計算利潤
if 利潤大於 0
累加利潤
將最小價格設成今天價格 (因為題目要求可以當天賣之後再買)
return 累加的利潤

  • 如果你用 C# 可以利用我的 測試程式 來驗證

  • 如果你用 Java or Python or C++ 可上 LeetCode Online Judge 驗證

  • 還是想不出來嗎?參考我的 解答(C#版本) 或 [解答(Java版本) 吧!

    public int maxProfit(int[] prices)
    {
    if (prices.Length <= 1) return 0;

     int totalProft = 0;
     int minPrice = prices[0];
     foreach (var currentPrice in prices)
     {
         if (currentPrice < minPrice)
             minPrice = currentPrice;
         int profit = currentPrice - minPrice;
         if (profit > 0)
         {
             totalProft += profit;
             minPrice = currentPrice;
         }
     }
    
     return totalProft;
    

    }


上一篇
[Day03] 股市中最佳買賣時機-I
下一篇
[Day05] 二元樹的的中序走訪
系列文
連續30天,挑戰演算法30

尚未有邦友留言

立即登入留言