LeetCode[贪心算法] - #122 Best Time to Buy and Sell Stock II

原题链接：#122 Best Time to Buy and Sell Stock II

 

要求：

假定你有一个包含n个元素的整型数组，其中的第i个元素是指定股票在第i天的价格。

设计一个算法来计算在这n天里可能获得的最大利润。注：只考虑单只该股票的买入和卖出时机，一天内可以买卖多次，但不允许同一时间内存在多次交易（即：再次买入之前，必须买入该股票）

 

难度：中等

 

分析：

贪心算法：在对问题求解时，总是做出在当前看来最好的选择。即：不从整体上最优加以考虑，只求局部最优解。

对于此题情境，获得可能的最大利润的手段为：买入后的次日，只要股价上涨就卖出。同时如果后一天股价下跌则前一天不买入。后一条如果没有时间机器任谁也无法事先知道。所以下面解法只能用于在n天中每天股价都已知的情况下求个理想值，并不能用于指导实际。

 

解决方案：

Java - 2 ms

    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        for(int i=prices.length-1; i>0; i--){
            if(prices[i-1]>=prices[i]){
                continue;
            }else {
                maxProfit += prices[i]-prices[i-1];
            }
        }
        return maxProfit;
    }

简单测试程序