資訊專欄INFORMATION COLUMN
摘要：示例輸入輸出解釋對應的交易狀態為買入賣出冷凍期買入賣出思路這道題使用動態規劃。狀態表示當天休息能夠獲得的最大價值，表示當天持有股票能夠獲得的最大價值，表示當天持有股票能夠獲得的最大價值。
Description
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 (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day).
Example:
Input: [1,2,3,0,2] Output: 3 Explanation: transactions = [buy, sell, cooldown, buy, sell]描述
給定一個整數數組，其中第 i 個元素代表了第 i 天的股票價格 。?
設計一個算法計算出最大利潤。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:
你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。
示例:
輸入: [1,2,3,0,2] 輸出: 3 解釋: 對應的交易狀態為: [買入, 賣出, 冷凍期, 買入, 賣出]思路
這道題使用動態規劃。
狀態：colldown 表示當天休息能夠獲得的最大價值，hold 表示當天持有股票能夠獲得的最大價值，sold 表示當天持有股票能夠獲得的最大價值。
初始狀態：colldown = 0, hold = －∞, sold = 0。
狀態轉移方程：colldown ：如果當前休息，那么當前的價值可以來自于前一天休息或者前一天賣出股票（前一天買進股票不會產生收益），所以 colldown = max(colldown, sold)；hold ：如果當天選擇繼續持有股票，則當天可以選擇繼續持有昨天的股票，或者昨天休息今天買進股票，所以hold = max(oldhold, colldown - prices[i]); sold :當天賣出股票，則其價值只能來自于昨天買進今天賣出 sold = oldhold + prices[i]。
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-02-13 14:21:33
# @Last Modified by: 何睿
# @Last Modified time: 2019-02-13 17:36:21
import sys
class Solution:
def maxProfit(self, prices: "List[int]") -> "int":
# 少于兩天無法進行交易
if len(prices) < 2: return 0
colldown, hold, sold = 0, -sys.maxsize, 0
for day in range(len(prices)):
oldhold = hold
# 當天持有：當天可以什么都不做，持有昨天持有的股票
# 或者當天買進股票
# 所以：當天價值可以來自前一天持有的價值，或者前一天休息今天買入的價值
hold = max(oldhold, colldown - prices[day])
# 當天休息：當天的價值可以來自于前一天休息的價值
# 或者前一天賣出的價值
colldown = max(colldown, sold)
# 當天賣出：當前價值來自前一天持有加上今天的價值
sold = oldhold + prices[day]
return max(colldown, sold)
源代碼文件在這里.
?本文首發于何睿的博客，歡迎轉載，轉載需保留文章來源，作者信息和本聲明.
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/43186.html
摘要：題目鏈接來解，要用兩個分別表示現在的操作是還是，優化空間用滾動數組，或者幾個 309. Best Time to Buy and Sell Stock with Cooldown 題目鏈接：https://leetcode.com/problems... dp來解，要用兩個dp array分別表示現在的操作是buy還是sell，優化空間用滾動數組，或者幾個int public clas...
摘要：分析因為當前日期買賣股票會受到之前日期買賣股票行為的影響，首先考慮到用解決。所以我們可以用兩個數組分別記錄當前持股跟未持股的狀態。 Best Time to Buy and Sell Stock with Cooldown Say you have an array for which the ith element is the price of a given stock on ...
摘要：關鍵字，，算法，，動態規劃，上關于主題的題目有四個這四個題目難度依次遞增。其中第四個問題是尋求一個通解，在給定和最大買賣次數的情況下，求最大收益。首先大致的解題方向是動態規劃，這個應該不難想到。之后就是怎么找到狀態，怎么列狀態轉移方程。 關鍵字：leetcode，Best Time To Buy And Sell Stock，算法，algorithm，動態規劃，dynamic prog...
摘要：求可能的最大利潤題目給了兩個例子最大利潤就是進價為，賣價為的時候，利潤為在這個案例中，進價一直高于售價，所以無法成交，返回。主要注意一下，先買入才能賣出賣價一定要比買入價格高才能成交就可以了。 題目詳情 Say you have an array for which the ith element is the price of a given stock on day i.If yo...
摘要：題目要求有一個整數數組，每一位上的值代表那一天的股票價格。現在假設最多能夠進行次交易，問最大的收入是多少思路和代碼這里采用了動態編程的思想。 題目要求 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 t...
閱讀 2342·2021-11-24 09:39
閱讀 3788·2021-11-19 09:40
閱讀 2156·2021-09-27 13:36
閱讀 1902·2019-08-30 15:44
閱讀 397·2019-08-30 13:52
閱讀 2716·2019-08-30 11:13
閱讀 2187·2019-08-29 16:18
閱讀 1763·2019-08-29 15:43
