Posted on 2013-04-25 22:22
小明 閱讀(2075)
評論(0) 編輯 收藏 所屬分類:
數據結構和算法
分析：
這道題相比之前的兩道題，難度提高了不少。
因為限制了只能交易兩次，所以我們可以把n天分為兩段，分別計算這兩段的最大收益，就可以得到一個最大收益。窮舉所有這樣的分法，就可以得到全局的最大收益。
為了提高效率，這里使用動態規劃，即把中間狀態記錄下來。使用了兩個數組profits，nprofits分別記錄從0..i和i..n的最大收益。
代碼如下：
public int maxProfit(
int[] prices) {
int days = prices.length;
if(days<2){
return 0;
}
int[] profits =
new int[days];
int min = prices[0];
int max = min;
for(
int i=1;i<days;++i){
int p = prices[i];
if(min>p){
max = min = p;
}
else if(max<p){
max = p;
}
int profit = max - min;
profits[i] = (profits[i-1]>profit)?profits[i-1]:profit;
}
int[] nprofits =
new int[days];
nprofits[days-1] = 0;
max = min = prices[days-1];
for(
int i=days-2;i>=0;--i){
int p = prices[i];
if(min>p){
min =p;
}
else if(max<p){
max = min = p;
}
int profit = max - min;
nprofits[i] = (nprofits[i+1]>profit)?nprofits[i+1]:profit;
}
int maxprofit = 0;
for(
int i=0;i<days;++i){
int profit = profits[i]+nprofits[i];
if(maxprofit<profit){
maxprofit = profit;
}
}
return maxprofit;
}