Best Time to Buy and Sell Stock II

Best Time to Buy and Sell Stock II

 

Say you have an array for which the i^th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Naive Way: 这个感觉这样一改就跟原题不是一个套路了。很直观的感觉就是，买，直到下一个不是递增的，卖。一开始应该得先找到第一个递增区间的起点。

算法复杂度是O(n)

public class Solution {
    public int maxProfit(int[] prices) {
        int opt = 0;
        int begin = 0, end = 0;
        while(end + 1< prices.length){
            begin = end+1;
            while(begin < prices.length){
                if(prices[begin] > prices[begin-1])
                    break;
                begin++;
            }
            begin--;
            end = begin;
            while(end + 1 < prices.length){
                if(prices[end+1] < prices[end])
                    break;
                end++;
            }
            opt += prices[end] - prices[begin];
        }
        return opt;
    }
}


Improved Way: Discuss里有一种Greedy的算法，很好。一旦有股票的价格比前一天的高，就可以加上这个差价，即能赚就买。因为比如：
1  2  3  4  5
max profit = 5-1 = 4;
greedy      = 5-4 + 4-3 + 3-2 + 2-1 = 4;

虽然题目不让在同一天买卖，但实际上在递增的区间中同一天买卖和第一天买最后一天卖是一样。这是否也说明了炒股票应该见好就收呢。

public class Solution {
    public int maxProfit(int[] prices) {
        int opt = 0;
        int p = 0;
        while(++p < prices.length){
            opt += Math.max(prices[p]-prices[p-1],0);
        }
        return opt;
    }
}