問題:
假設你有一個陣列,該陣列第 i 個元素代表第 i 天股票的價格,並且你指有一次買賣的機會,請設計一個演算法求得最大的力論為何?
例子
想法:
這一題其實如果懂題目,其實還滿簡單的。他主要就是要你再該陣列中找出最大值和最小值的差而已!只不過,因為股票是不能在 未來買 並且到 過去賣,因此這 最大/最小值 的 差 還多了一個限制就是,最大值的 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# 基本上不會差太多,非常類似