【LeetCode 122】买卖股票的最佳时机 II

122. Best Time to Buy and Sell Stock II

Difficulty: Easy

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 1:

**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 = 3.

Example 2:

**Input:** [1,2,3,4,5]
**Output:** 4
**Explanation:** Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

1
2
3

**Input:** [7,6,4,3,1]
**Output:** 0
**Explanation:** In this case, no transaction is done, i.e. max profit = 0.

解题思路

注意边界条件的判断，当到达数组末尾后，如果持有股票需要卖出

Solution

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) == 0:
            return 0
        buy_price = prices[0]
        is_hold = False
        money = 0
        for index in range(1, len(prices)):
            if prices[index] < prices[index - 1] and is_hold:
                money = money + (prices[index - 1] - buy_price)
                is_hold = False
            elif prices[index] > prices[index - 1] and not is_hold:
                buy_price = prices[index - 1]
                is_hold = True
            if index + 1 == len(prices) and is_hold:
                money = money + prices[index] - buy_price

        return money