122_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 (i.e., buy one and sell one share of the stock multiple times).

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

Example:

Input:
 [7,1,5,3,6,4]

Output:
 7

Explanation:
 Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3

Solution:

Idea:

• catch all the valley and peak, add all the slope into profit

  • loop over all the elements, initiate minprice and maxprice as the first element

    • if the next element is larger than maxprice , update maxprice with the current element

    • if the next element is smaller than maxprice, a new valley starts. Add the last profit into total profit and update minprice and maxprice be the current element.

Time Complexity: $O(n)$

Space Complexity: $O(1)$

def maxProfit(self, prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    if len(prices) < 2 :
        return 0

    min_price = max_price = prices[0]
    profit = 0
    for i in range(1, len(prices)) :
        if prices[i] < max_price :
            profit += max_price - min_price
            min_price = max_price = prices[i]
        else :
            max_price = prices[i]
    profit += max_price - min_price
    return profit