You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can sell and buy the stock multiple times on the same day, ensuring you never hold more than one share of the stock.
Find and return the maximum profit you can achieve.
Example 1:
Input: prices = [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. Total profit is 4 + 3 = 7.
Example 2:
Input: prices = [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. Total profit is 4.
Example 3:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
Constraints:
1 <= prices.length <= 3 * 1040 <= prices[i] <= 104
这道题是很典型的DP问题，DP问题在于创建一个“状态”转换的系统。而不是根据“行动”来找规律。
很容易会想到我们每天可以“买，卖，Hold”，试图根据行动来找规律。然而实际上每次行动的前置条件复杂，判断过于多。比如我第三天能不能卖。取决于我前一天买没买，或者取决于我第一天买，第二天天Hold也是可以的，这就造成了当天行动无法只根据前一天的行动来判断
而我们如果根据状态来建立机制就简单多了。
我们每天结束只可能有两种状态：有股票，没股票。而当天有无股票只根据前一天的状态来：
状态1：前一天：有股票 -> 卖 -> 当天：无股票
状态2：前一天：无股票 -> 保持 -> 当天：无股票
状态3：前一天：有股票 -> 保持 -> 当天：有股票
状态4：前一天：无股票 -> 买 -> 当天：有股票
当建立这样的系统之后我们可以用两个参数： notHold，hold来储存每天结束后的price
状态转换可以写成如下代码
temp = hold
hold = max(notHold - prices[i], hold) #状态4， 状态3
notHold = max(temp + prices[i], notHold) #状态1， 状态2我比较想不通的点：我们在这里丢掉了一个状态，而那个数值（当前price）较小的状态会不会对以后产生影响，比如在无股票时price较小的保持状态会不会让未来产生更大的收益？
其实这个是不存在的，因为假设我们第n天丢掉一个比较小的price的状态，在第n+1天到最后一天一定会有一个最大数值（price），而第n天和之后状态的最大数值加起来达到最大的话必须要求第n天的状态也是最大的。
整个代码如下：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# hold - -7 nothold - 0
hold = -prices[0]
notHold = 0
for i in range(1, len(prices)):
temp = hold
hold = max(notHold - prices[i], hold)
notHold = max(temp + prices[i],notHold)
return max(hold, notHold)
文章评论