{"id":3419,"date":"2020-04-01T12:16:26","date_gmt":"2020-04-01T04:16:26","guid":{"rendered":"http:\/\/www.sniper97.cn\/?p=3419"},"modified":"2020-04-01T12:16:26","modified_gmt":"2020-04-01T04:16:26","slug":"%e3%80%90leetcode%e3%80%910123-%e4%b9%b0%e5%8d%96%e8%82%a1%e7%a5%a8%e7%9a%84%e6%9c%80%e4%bd%b3%e6%97%b6%e6%9c%ba","status":"publish","type":"post","link":"http:\/\/www.sniper97.cn\/index.php\/note\/algorithm\/3419\/","title":{"rendered":"\u3010LeetCode\u3011*0123 \u4e70\u5356\u80a1\u7968\u7684\u6700\u4f73\u65f6\u673a"},"content":{"rendered":"\n

https:\/\/leetcode-cn.com\/problems\/best-time-to-buy-and-sell-stock-iii\/<\/a><\/p>\n\n\n

# -*- coding:utf-8 -*-

\"\"\"
<\/em>      \u250f\u251b \u253b\u2501\u2501\u2501\u2501\u2501\u251b \u253b\u2513
<\/em>      \u2503<\/em>\u3000\u3000\u3000\u3000\u3000\u3000<\/em> \u2503
<\/em>      \u2503<\/em>\u3000\u3000\u3000<\/em>\u2501<\/em>\u3000\u3000\u3000<\/em>\u2503
<\/em>      \u2503<\/em>\u3000<\/em>\u2533\u251b<\/em>\u3000<\/em>  \u2517\u2533<\/em>\u3000<\/em>\u2503
<\/em>      \u2503<\/em>\u3000\u3000\u3000\u3000\u3000\u3000<\/em> \u2503
<\/em>      \u2503<\/em>\u3000\u3000\u3000<\/em>\u253b<\/em>\u3000\u3000\u3000<\/em>\u2503
<\/em>      \u2503<\/em>\u3000\u3000\u3000\u3000\u3000\u3000<\/em> \u2503
<\/em>      \u2517\u2501\u2513<\/em>\u3000\u3000\u3000<\/em>\u250f\u2501\u2501\u2501\u251b
<\/em>        \u2503<\/em>\u3000\u3000\u3000<\/em>\u2503   <\/em>\u795e\u517d\u4fdd\u4f51<\/em>
<\/em>        \u2503<\/em>\u3000\u3000\u3000<\/em>\u2503   <\/em>\u4ee3\u7801\u65e0<\/em>BUG<\/em>\uff01<\/em>
<\/em>        \u2503<\/em>\u3000\u3000\u3000<\/em>\u2517\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2513
<\/em>        \u2503<\/em>\u3000\u3000\u3000\u3000\u3000\u3000\u3000<\/em>    \u2523\u2513
<\/em>        \u2503<\/em>\u3000\u3000\u3000\u3000<\/em>         \u250f\u251b
<\/em>        \u2517\u2501\u2513 \u2513 \u250f\u2501\u2501\u2501\u2533 \u2513 \u250f\u2501\u251b
<\/em>          \u2503 \u252b \u252b   \u2503 \u252b \u252b
<\/em>          \u2517\u2501\u253b\u2501\u251b   \u2517\u2501\u253b\u2501\u251b
<\/em>\"\"\"
<\/em>
<\/em>
<\/em>class Solution(object):
    def maxProfit(self, prices):
        \"\"\"
<\/em>        <\/em>:type<\/em><\/strong> prices: List[int]
<\/em>        <\/em>:rtype<\/em><\/strong>: int
<\/em>        \"\"\"
<\/em>        <\/em>if prices == []:
            return 0
        length = len(prices)
        # \u7ed3\u675f\u65f6\u7684\u6700\u9ad8\u5229\u6da6=[\u5929\u6570][\u662f\u5426\u6301\u6709\u80a1\u7968][\u5356\u51fa\u6b21\u6570]
        dp = [[[0, 0, 0], [0, 0, 0]] for i in range(0, length)]
        # \u7b2c\u4e00\u5929\u4f11\u606f
        dp[0][0][0] = 0
        # \u7b2c\u4e00\u5929\u4e70\u5165
        dp[0][1][0] = -prices[0]
        # \u7b2c\u4e00\u5929\u4e0d\u53ef\u80fd\u5df2\u7ecf\u6709\u5356\u51fa
        dp[0][0][1] = float('-inf')
        dp[0][0][2] = float('-inf')
        # \u7b2c\u4e00\u5929\u4e0d\u53ef\u80fd\u5df2\u7ecf\u5356\u51fa
        dp[0][1][1] = float('-inf')
        dp[0][1][2] = float('-inf')
        for i in range(1, length):
            # \u672a\u6301\u80a1\uff0c\u672a\u5356\u51fa\u8fc7\uff0c\u8bf4\u660e\u4ece\u672a\u8fdb\u884c\u8fc7\u4e70\u5356
            dp[i][0][0] = 0
            # \u672a\u6301\u80a1\uff0c\u5356\u51fa\u8fc71\u6b21\uff0c\u53ef\u80fd\u662f\u4eca\u5929\u5356\u7684\uff0c\u53ef\u80fd\u662f\u4e4b\u524d\u5356\u7684
            dp[i][0][1] = max(dp[i - 1][1][0] + prices[i], dp[i - 1][0][1])
            # \u672a\u6301\u80a1\uff0c\u5356\u51fa\u8fc72\u6b21\uff0c\u53ef\u80fd\u662f\u4eca\u5929\u5356\u7684\uff0c\u53ef\u80fd\u662f\u4e4b\u524d\u5356\u7684
            dp[i][0][2] = max(dp[i - 1][1][1] + prices[i], dp[i - 1][0][2])
            # \u6301\u80a1\uff0c\u672a\u5356\u51fa\u8fc7\uff0c\u53ef\u80fd\u662f\u4eca\u5929\u4e70\u7684\uff0c\u53ef\u80fd\u662f\u4e4b\u524d\u4e70\u7684
            dp[i][1][0] = max(dp[i - 1][0][0] - prices[i], dp[i - 1][1][0])
            # \u6301\u80a1\uff0c\u5356\u51fa\u8fc71\u6b21\uff0c\u53ef\u80fd\u662f\u4eca\u5929\u4e70\u7684\uff0c\u53ef\u80fd\u662f\u4e4b\u524d\u4e70\u7684
            dp[i][1][1] = max(dp[i - 1][0][1] - prices[i], dp[i - 1][1][1])
            # \u6301\u80a1\uff0c\u5356\u51fa\u8fc72\u6b21\uff0c\u4e0d\u53ef\u80fd
            dp[i][1][2] = float('-inf')
        return max(dp[length - 1][0][1], dp[length - 1][0][2], 0)


if __name__ == '__main__':
    prices = [3, 3, 5, 0, 0, 3, 1, 4]
    print(Solution().maxProfit(prices))
<\/pre>\n\n\n
\u601d\u8def\uff1a<\/strong>\u5f00\u59cb\u6709\u70b9\u81ea\u95ed\u4e86\uff0c\u597d\u96be\u554aemm\u3002<\/p>\n\n\n
\u8fd9\u4e2a\u521a\u5f00\u59cb\u80af\u5b9a\u662f\u786e\u5b9e\u52a8\u6001\u89c4\u5212\u7684\uff0c\u5c31\u662f\u72b6\u6001\u592a\u96be\u627e\u4e86\uff0c\u5c1d\u8bd5\u8fc7\u4e09\u7ef4\u6570\u7ec4\u6253\u72b6\u6001\u5931\u8d25\u4e86\uff08\u786e\u5b9e\u53ef\u4ee5\u7528\u4e09\u7ef4\u6570\u7ec4\u6253\u72b6\u6001\uff0c\u4f46\u662f\u6211\u592a\u83dc\u4e86\uff0c\u6ca1\u6363\u817e\u51fa\u6765\uff09\u3002\u7136\u540e\u5c31\u662f\u4e0a\u9762\u8fd9\u4e2a\u65b9\u6cd5\u3002<\/p>\n\n\n
\u5509\uff0c\u5b66\u65e0\u6b62\u5883\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
https:\/\/leetcode-cn.com\/problems\/best-time-to-buy- […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_mi_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[10],"tags":[],"views":5602,"_links":{"self":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/3419"}],"collection":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/comments?post=3419"}],"version-history":[{"count":0,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/3419\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/media?parent=3419"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/categories?post=3419"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/tags?post=3419"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}