[思路]LeetCode Problems-121. Best Time to Buy and Sell Stock
此篇文章要探討的問題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.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example 1:
Input: [7, 1, 5, 3, 6, 4] Output: 5 max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1] Output: 0 In this case, no transaction is done, i.e. max profit = 0.
首先要思考的是:我們自己是如何判別怎樣算賺錢呢?
對投資者來說,股票賺錢的本質就只是低買高賣,所以重要的往往不是單一的價格本身,而是兩個價格之間的差為多少?
因此,以題目的範例來說,我們感興趣的不是陣列中[7,1,5,3,6,4]的每個值,而是前後兩兩之間的差:
[ (1-7) , (5-1) , (3-5) , (6-3) , (4-6) ] = [ -6 , 4 , -2 , 3 , -2 ]
接者就可以再進一步判斷,
要從哪一個數開始作連續相加,並要停在哪一個數值上呢?
例如假設是要從-6開始加到4,-2,3的值,還是要從4開始連續加到-2,3的值?
處理序列的連續相加問題,我們可以用一個int整數來當暫存(假設最大獲利值),並且用for迴圈來run整個序列.
而要求出這個[ -6 , 4 , -2 , 3 , -2 ]價格差的陣列還需要再一個for迴圈完成,所以此題的解法是要用雙重FOR迴圈來解決:
(1).初始一個int當作最大獲利值
int maxprofit = 0;
(2)第一個for迴圈用來當作買進點
for (int i = 0; i < pricesSize - 1; i++) {}
(3)於for迴圈中再包含第二個for迴圈來找賣出點,並求出兩點間彼此的差值為多少
for (int i = 0; i < pricesSize - 1; i++) {
for (int j = i + 1; j < pricesSize; j++) {
int profit = prices[j] - prices[i];
}
}
(4)在第二個for迴圈中假如有找到差值比原先的最大獲利值還要大,則取代掉當作新的最大獲利值
int maxprofit = 0;
for (int i = 0; i < pricesSize - 1; i++) {
for (int j = i + 1; j < pricesSize; j++) {
int profit = prices[j] - prices[i];
if (profit > maxprofit)
maxprofit = profit;
}
}
(5)求出後最後傳回本題的答案.
最後完整程式碼如下:
int maxProfit(int* prices, int pricesSize) {
int maxprofit = 0;
for (int i = 0; i < pricesSize - 1; i++) {
for (int j = i + 1; j < pricesSize; j++) {
int profit = prices[j] - prices[i];
if (profit > maxprofit)
maxprofit = profit;
}
}
return maxprofit;
}
在此你可以看到其程式的效率是低的驚人,
因為雖然這解法直覺許多,
但是整體的時間複雜度是O(n^2),運算量十分地大.
而關於這種問題我們也可以稱其為Maximum subarray problem最大子數列問題
在陣列的單一方向找到一個連續的子數列，使該子數列的和最大
可以用演算法Kadane's Algorithm來解決:(From Wiki)
Kadane算法掃描一次整個數列的所有數值，在每一個掃描點計算以該點數值為結束點的子數列的最大和（正數和）。
該子數列由兩部分組成：以前一個位置為結束點的最大子數列、該位置的數值。因為該算法用到了「最佳子結構」（以每個位置為終點的最大子數列都是基於其前一位置的最大子數列計算得出），該算法可看成動態規劃的一例。
留言
張貼留言