小明思考

Just a software engineer
posts - 124, comments - 36, trackbacks - 0, articles - 0
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

最佳的股票买卖时间III

Posted on 2013-04-25 22:22 小明 阅读(2049) 评论(0)  编辑  收藏 所属分类: 数据结构和算法
问题假设你有一个数组包含了每天的股票价格,它的第i个元素就是第i天的股票价格。 

设计一个算法寻找最大的收益。你可以最多进行两次交易。
注意:你不能同时进行多次交易,也就是说你买股票之前,必须卖掉手中股票。


分析:
这道题相比之前的两道题,难度提高了不少。

因为限制了只能交易两次,所以我们可以把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;        
    }

只有注册用户登录后才能发表评论。


网站导航: