iT邦幫忙

DAY 3
0

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

[Day03] 股市中最佳買賣時機-I

題目來源:[LeetCode Online Judge]

問題:

假設你有一個陣列,該陣列第 i 個元素代表第 i 天股票的價格,並且你指有一次買賣的機會,請設計一個演算法求得最大的力論為何?

例子

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

想法:

這一題其實如果懂題目,其實還滿簡單的。他主要就是要你再該陣列中找出最大值和最小值的差而已!只不過,因為股票是不能在 未來買 並且到 過去賣,因此這 最大/最小值 的 還多了一個限制就是,最大值的 index 必須大於 最小值的 index。所以,這樣下在整個題目就變的簡單很多了!
另外,題目沒有說到該陣列最大或最小會是多少(也就是沒有限至股市的資料一共多少天),因此我們也必須處理陣列個數(股市天數)小於或等於 1 的情況。

解法:

for 從第一天到最後一天
若今天的價個比最低價還低,保存今天價格為最低價
若 今天價格 減掉 最低價格 大於 最大利潤 則 保存 最大利潤
回傳 最大利潤


我的答案

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

    int minPrice = prices[0];
    for (int i = 0; i < prices.Length; i++)
    {
        if (prices[i] < minPrice)
            minPrice = prices[i];
        int pridictProfit = prices[i] - minPrice;
        if (pridictProfit > maxProfit)
            maxProfit = pridictProfit;
    }

    return maxProfit;
}

我的測試程式

當然你也可以到 [LeetCode OJ][BestTimeToByStock] 去試試看,不過他目前只接受 Java, C++ 或 Python. 但是 Java 和 C# 基本上不會差太多,非常類似


上一篇
[Day02] 在PTT看到的排隊問題
下一篇
[Day04] 股市中最佳買賣時機-II
系列文
連續30天,挑戰演算法30

尚未有邦友留言

立即登入留言