Leetcode 122 best time to buy and sell stock II

Leetcode 122

June 5, 2018
10:16 p

Julia spent less than 20 minutes to go over solution using peak and valley, solve the algorithm using
solution II on leetcode website|:
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/solution/


The key point is we need to consider every peak immediately following a valley to maximize the profit.
In case we skip one of the peaks (trying to obtain more profit), we will end up losing the profit over 
one of the transactions leading to an overall lesser profit.

For example, in the above case, if we skip peak_ipeak
​i
​​  and valley_jvalley
​j
​​  trying to obtain more profit by considering points with more difference in heights, the net profit 
obtained will always be lesser than the one obtained by including them, since CC will always be lesser 
than A+BA+B.

class Solution {
    public int maxProfit(int[] prices) {
        int i = 0;
        int valley = prices[0];
        int peak = prices[0];
        int maxprofit = 0;
        while (i < prices.length - 1) {
            while (i < prices.length - 1 && prices[i] >= prices[i + 1])
                i++;
            valley = prices[i];
            while (i < prices.length - 1 && prices[i] <= prices[i + 1])
                i++;
            peak = prices[i];
            maxprofit += peak - valley;
        }
        return maxprofit;
    }
}



Java

class Solution {
    public int maxProfit(int[] prices) {
        int i = 0;
        int valley = prices[0];
        int peak = prices[0];
        int maxprofit = 0;
        while (i < prices.length - 1) {
            while (i < prices.length - 1 && prices[i] >= prices[i + 1])
                i++;
            valley = prices[i];
            while (i < prices.length - 1 && prices[i] <= prices[i + 1])
                i++;
            peak = prices[i];
            maxprofit += peak - valley;
        }
        return maxprofit;
    }
}