Best Time to Buy and Sell Stock II

假设时间可以倒流,每天的stock price被放在相应的array里prices[],那么最大的收益可能是多少
想法:从初始元素开始,先找到最低点,然后从最低点开始,找下一个最高点,两者相减得到一个差。然后再从这个最高点开始,找下一个最低点,和最高点,相减得到差继续与之前的差累加起来,直到array的最后,就可以得到最大的profit。最后需要注意的是结束时,如果最后一个点是低点(之前一个找到的是最高点,然后走势一直向下),则不买卖,profit不计入在内。如果想法最后一个是高点,那么需要计算最后一个点(高点)和之前一个找到的低点的差,并累加进最后的profit里

Code如下:

public class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        int low = 0, high = 0, index = 0;
        while(index < prices.length)
        {
            low = findNextLow(prices, index);
            index = low + 1;
            if (index == prices.length)
                break;
            high = findNextHigh(prices, index);
            max += prices[high] - prices[low];
            index = high + 1;
        }
        return max;
    }
    
    public int findNextLow(int[] prices, int start) // return next position that is lowest, otherwise return the last position
    {
        for (int i = start; i < prices.length-1; i++)
        {
            if (prices[i+1] > prices[i])
            {
                return i;
            }
        }
        return prices.length - 1;
    }
    
    public int findNextHigh(int[] prices, int start)
    {
        for (int i = start; i < prices.length-1; i++)
        {
            if (prices[i+1] < prices[i])
            {
                return i;
            }
        }
        return prices.length - 1;
    }
}

还有动态规划的办法,因为我们不限制买卖次数,只要从头到尾扫描一遍price,只要price[i] > price[i-1], 那么这个profit就可以计入到最后的profit里面

Second Submission:

Very simple, Since the number of transactions are not limited, we just scan the whole array, when price[i+1] > price[i], and simply add the diff in to the profit

public class Solution {
    public int maxProfit(int[] prices) {
        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;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s