資訊專欄INFORMATION COLUMN
摘要：示例輸入輸出解釋對(duì)應(yīng)的交易狀態(tài)為買入賣出冷凍期買入賣出思路這道題使用動(dòng)態(tài)規(guī)劃。狀態(tài)表示當(dāng)天休息能夠獲得的最大價(jià)值，表示當(dāng)天持有股票能夠獲得的最大價(jià)值，表示當(dāng)天持有股票能夠獲得的最大價(jià)值。
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]描述
給定一個(gè)整數(shù)數(shù)組，其中第 i 個(gè)元素代表了第 i 天的股票價(jià)格 。?
設(shè)計(jì)一個(gè)算法計(jì)算出最大利潤(rùn)。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:
你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買前出售掉之前的股票）。
賣出股票后，你無(wú)法在第二天買入股票 (即冷凍期為 1 天)。
示例:
輸入: [1,2,3,0,2] 輸出: 3 解釋: 對(duì)應(yīng)的交易狀態(tài)為: [買入, 賣出, 冷凍期, 買入, 賣出]思路
這道題使用動(dòng)態(tài)規(guī)劃。
狀態(tài)：colldown 表示當(dāng)天休息能夠獲得的最大價(jià)值，hold 表示當(dāng)天持有股票能夠獲得的最大價(jià)值，sold 表示當(dāng)天持有股票能夠獲得的最大價(jià)值。
初始狀態(tài)：colldown = 0, hold = －∞, sold = 0。
狀態(tài)轉(zhuǎn)移方程：colldown ：如果當(dāng)前休息，那么當(dāng)前的價(jià)值可以來(lái)自于前一天休息或者前一天賣出股票（前一天買進(jìn)股票不會(huì)產(chǎn)生收益），所以 colldown = max(colldown, sold)；hold ：如果當(dāng)天選擇繼續(xù)持有股票，則當(dāng)天可以選擇繼續(xù)持有昨天的股票，或者昨天休息今天買進(jìn)股票，所以hold = max(oldhold, colldown - prices[i]); sold :當(dāng)天賣出股票，則其價(jià)值只能來(lái)自于昨天買進(jìn)今天賣出 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":
# 少于兩天無(wú)法進(jìn)行交易
if len(prices) < 2: return 0
colldown, hold, sold = 0, -sys.maxsize, 0
for day in range(len(prices)):
oldhold = hold
# 當(dāng)天持有：當(dāng)天可以什么都不做，持有昨天持有的股票
# 或者當(dāng)天買進(jìn)股票
# 所以：當(dāng)天價(jià)值可以來(lái)自前一天持有的價(jià)值，或者前一天休息今天買入的價(jià)值
hold = max(oldhold, colldown - prices[day])
# 當(dāng)天休息：當(dāng)天的價(jià)值可以來(lái)自于前一天休息的價(jià)值
# 或者前一天賣出的價(jià)值
colldown = max(colldown, sold)
# 當(dāng)天賣出：當(dāng)前價(jià)值來(lái)自前一天持有加上今天的價(jià)值
sold = oldhold + prices[day]
return max(colldown, sold)
源代碼文件在這里.
?本文首發(fā)于何睿的博客，歡迎轉(zhuǎn)載，轉(zhuǎn)載需保留文章來(lái)源，作者信息和本聲明.
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/43186.html
摘要：題目鏈接來(lái)解，要用兩個(gè)分別表示現(xiàn)在的操作是還是，優(yōu)化空間用滾動(dòng)數(shù)組，或者幾個(gè) 309. Best Time to Buy and Sell Stock with Cooldown 題目鏈接：https://leetcode.com/problems... dp來(lái)解，要用兩個(gè)dp array分別表示現(xiàn)在的操作是buy還是sell，優(yōu)化空間用滾動(dòng)數(shù)組，或者幾個(gè)int public clas...
摘要：分析因?yàn)楫?dāng)前日期買賣股票會(huì)受到之前日期買賣股票行為的影響，首先考慮到用解決。所以我們可以用兩個(gè)數(shù)組分別記錄當(dāng)前持股跟未持股的狀態(tài)。 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 ...
摘要：關(guān)鍵字，，算法，，動(dòng)態(tài)規(guī)劃，上關(guān)于主題的題目有四個(gè)這四個(gè)題目難度依次遞增。其中第四個(gè)問(wèn)題是尋求一個(gè)通解，在給定和最大買賣次數(shù)的情況下，求最大收益。首先大致的解題方向是動(dòng)態(tài)規(guī)劃，這個(gè)應(yīng)該不難想到。之后就是怎么找到狀態(tài)，怎么列狀態(tài)轉(zhuǎn)移方程。 關(guān)鍵字：leetcode，Best Time To Buy And Sell Stock，算法，algorithm，動(dòng)態(tài)規(guī)劃，dynamic prog...
摘要：求可能的最大利潤(rùn)題目給了兩個(gè)例子最大利潤(rùn)就是進(jìn)價(jià)為，賣價(jià)為的時(shí)候，利潤(rùn)為在這個(gè)案例中，進(jìn)價(jià)一直高于售價(jià)，所以無(wú)法成交，返回。主要注意一下，先買入才能賣出賣價(jià)一定要比買入價(jià)格高才能成交就可以了。 題目詳情 Say you have an array for which the ith element is the price of a given stock on day i.If yo...
摘要：題目要求有一個(gè)整數(shù)數(shù)組，每一位上的值代表那一天的股票價(jià)格?，F(xiàn)在假設(shè)最多能夠進(jìn)行次交易，問(wèn)最大的收入是多少思路和代碼這里采用了動(dòng)態(tài)編程的思想。 題目要求 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...
閱讀 2372·2021-11-24 09:39
閱讀 3822·2021-11-19 09:40
閱讀 2198·2021-09-27 13:36
閱讀 1917·2019-08-30 15:44
閱讀 421·2019-08-30 13:52
閱讀 2738·2019-08-30 11:13
閱讀 2229·2019-08-29 16:18
閱讀 1794·2019-08-29 15:43
