Posted on 2013-04-25 22:22
小明 阅读(2056)
评论(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;
}