小明思考

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

最佳的股票买卖时间II

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

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

分析:为了得到最大收益,必须在所有上升的曲线段的开始点买入,在最高点卖出。而在下降阶段不出手。



实现代码如下:
public class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if(len<2){
            return 0;
        }
        
        int min=0;
        int result = 0;
        boolean inBuy = false;
        for(int i=0;i<len-1;++i){
            int p = prices[i];
            int q = prices[i+1];
            if(!inBuy){
                if(q>p){
                    inBuy = true;
                    min=p ;
                }
            }
            else{
                if(q<p){
                    result += (p-min);
                    inBuy = false;
                }
            }
        }
        if(inBuy){
            result += ((prices[len-1])-min);
        }
        return result;
    }
}

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


网站导航: