首页 > 其他 > 详细

【LeetCode】Best Time to Buy and Sell Stock II

时间:2014-05-10 00:24:37      阅读:350      评论:0      收藏:0      [点我收藏+]

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

这个更简单了,题目要求可以多次买卖,但是同一时间只能有一股在手里。
这样就可以在每次上升子序列之前买入,在上升子序列结束的时候卖出。相当于能够获得所有的上升子序列的收益。
而且,对于一个上升子序列,比如:5,1,2,3,4,0 中的1,2,3,4序列来说,对于两种操作方案:
一,在1买入,4卖出;
二,在1买入,2卖出同时买入,3卖出同时买入,4卖出;
这两种操作下,收益是一样的。


所以算法就是:从头到尾扫描prices,如果i比i-1大,那么price[i] – price[i-1]就可以计入最后的收益中。这样扫描一次O(n)就可以获得最大收益了。

bubuko.com,布布扣
public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==0||prices.length==1)
             return 0;
        int max = 0;
        for(int i=1;i<prices.length;i++){
            if(prices[i]>prices[i-1]){
                max+=(prices[i]-prices[i-1]);                
            }
                
                
        }
        return max;
        
    }
}
bubuko.com,布布扣

 

【LeetCode】Best Time to Buy and Sell Stock II,布布扣,bubuko.com

【LeetCode】Best Time to Buy and Sell Stock II

原文:http://www.cnblogs.com/yixianyixian/p/3718496.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!