[058] LeetCode 122演算法【Best Time to Buy and Sell Stock II】 股票機器人 II

122. Best Time to Buy and Sell Stock II (Easy)

Say you have an array for which the ith 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:

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

這一題是上一題的變型，差別在於買入次數可以是無限，所以從上一題的題型來看只要改變找出profit最大變成累加profit就可以解了，另一種解法是把他想像成曲線，我們要找到最低點當作買點，找到最高點當作賣點，也就是說當發現這個數字比前一個小的時候他就是買點，反之。

也可以用貪心，跟第一個解法一樣，只是差別要判斷一下長度。

大家加油。

2020/3/6更新，因為刷到DP的部分直接刷到另一條分支去了，所以後續沒有貼上來，加上公司剛好要上產品花了許多時間，但這邊私下已經刷了100多題，只是順序部分可能要大改一下，這邊請你各位先重新把這些基礎題目讀滿讀好，以後會用模板的方式教你各位刷題。

上一篇：[057] LeetCode 121 演算法【Best Time to Buy and Sell Stock】 股票機器人

下一篇：[059] LeetCode 123演算法【Best Time to Buy and Sell Stock III】 股票機器人 III