刷力扣遇到這個題了...
給定一個整數陣列 prices ，它的第 i 個元素 prices[i] 是一支給定的股票在第 i 天的價格。
設計一個演算法來計算你所能獲取的最大利潤。你最多可以完成 k 筆交易。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 1：
輸入：k = 2, prices = [2,4,1]
輸出：2
解釋：在第 1 天 (股票價格 = 2) 的時候買入，在第 2 天 (股票價格 = 4) 的時候賣出，這筆交易所能獲得利潤 = 4-2 = 2 。
示例 2：
輸入：k = 2, prices = [3,2,6,5,0,3]
輸出：7
解釋：在第 2 天 (股票價格 = 2) 的時候買入，在第 3 天 (股票價格 = 6) 的時候賣出, 這筆交易所能獲得利潤 = 6-2 = 4 。
隨后，在第 5 天 (股票價格 = 0) 的時候買入，在第 6 天 (股票價格 = 3) 的時候賣出, 這筆交易所能獲得利潤 = 3-0 = 3 。
看了不少解題思路, 一看三維dp就懵了... 后來自己憋出個解法, 用例有限, 也不知道對不對? 請大佬指點.
我的解法是這樣:
1.遍歷陣列獲得每個元素向前的最大差值；
2.遍歷差值集，尋找逆序。如果出現逆序，在此逆序對之間截斷：
a. 逆序對前元素為前一段的最大收益值；
b. 逆序對后元素為后一段的階梯，在后一段出現新逆序之前，收益值為當前元素 - 階梯；
c. 如果差值集尾部未出現逆序，則尾部元素 - 階梯為最后的最大收益值；
3.將各分段最大收益值排序，取前limited位sum即為結果；
整體時間復雜為O(nlogn), 空間O(n), 以下是java代碼:
/**
* 思路：三維dp看不懂。。。
* 1。遍歷陣列獲得每個元素向前的最大差值；
* 2。遍歷差值集，尋找逆序。如果出現逆序，此逆序對之間截斷：
* a. 逆序對前元素為前一段的最大收益值；
* b。逆序對后元素為后一段的階梯，在后一段出現新逆序之前，收益值為當前元素 - 階梯；
* c。如果差值集尾部未出現逆序，則尾部元素 - 階梯為最后的最大收益值；
* 3。將各分段最大收益值排序，取前limited位sum即為結果；
*/
@TestTimmer
public static int method_0(Integer[] prices, Integer limited) {
int result = 0;
if(Objects.nonNull(prices) && prices.length > 0 && limited > 0) {
//先計算出所有元素的最大差值；
int[] temp = new int[prices.length];
//之前的最小元素；
int min = prices[0];
for(int i = 1; i < prices.length; i++) {
min = Math.min(min, prices[i]);
temp[i] = prices[i] - min;
}
//遍歷最大差值，發現逆序出現則截斷，將最大值計入陣列；
int[] results = new int[prices.length >> 1];
min = 0;
int step = 0;
for(int j = 1; j < temp.length; j++) {
//出現逆序；
if(temp[j] < temp[j - 1]) {
results[min] = temp[j - 1] - step;
min++;
step = temp[j];
} else if(j == temp.length - 1) {
results[min] = temp[j] - step;
break;
}
}
//計算最大值；
if(limited >= results.length) {
result = IntStream.of(results).sum();
} else {
Arrays.sort(results);
for(int k = results.length - 1; k > results.length - limited - 1; k--) {
result += results[k];
}
}
}
return result;
}
在下演算法老白, 演算法名次認不全, 請大佬們指點.
@TestTimer 是我自己寫的測驗用注解,批量比較演算法時間空間消耗的. 忽略!!!忽略!!!
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/241541.html
標籤：數據結構與算法