LeetCode 309. Best Time to Buy and Sell Stock with

刘明发布于2019-07-31 10:04 / 1187人阅读

摘要：示例输入输出解释对应的交易状态为买入卖出冷冻期买入卖出思路这道题使用动态规划。状态表示当天休息能够获得的最大价值，表示当天持有股票能够获得的最大价值，表示当天持有股票能够获得的最大价值。

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)

源代码文件在这里.
©本文首发于何睿的博客，欢迎转载，转载需保留文章来源，作者信息和本声明.

私有云专线服务 redis Time to live Buy Sell Stock

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/43186.html

309. Best Time to Buy and Sell Stock with Cooldown

摘要：题目链接来解，要用两个分别表示现在的操作是还是，优化空间用滚动数组，或者几个 309. Best Time to Buy and Sell Stock with Cooldown 题目链接：https://leetcode.com/problems... dp来解，要用两个dp array分别表示现在的操作是buy还是sell，优化空间用滚动数组，或者几个int public clas...

sorra 2019-08-14 17:29 评论0 收藏0
[LeetCode]Best Time to Buy and Sell Stock with Coo

摘要：分析因为当前日期买卖股票会受到之前日期买卖股票行为的影响，首先考虑到用解决。所以我们可以用两个数组分别记录当前持股跟未持股的状态。 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 ...

xcc3641 2019-08-14 15:08 评论0 收藏0
Best Time To Buy And Sell Stock 买卖股票最佳时机

摘要：关键字，，算法，，动态规划，上关于主题的题目有四个这四个题目难度依次递增。其中第四个问题是寻求一个通解，在给定和最大买卖次数的情况下，求最大收益。首先大致的解题方向是动态规划，这个应该不难想到。之后就是怎么找到状态，怎么列状态转移方程。关键字：leetcode，Best Time To Buy And Sell Stock，算法，algorithm，动态规划，dynamic prog...

elliott_hu 2019-08-15 15:40 评论0 收藏0
leetcode 121 Best Time to Buy and Sell Stock

摘要：求可能的最大利润题目给了两个例子最大利润就是进价为，卖价为的时候，利润为在这个案例中，进价一直高于售价，所以无法成交，返回。主要注意一下，先买入才能卖出卖价一定要比买入价格高才能成交就可以了。题目详情 Say you have an array for which the ith element is the price of a given stock on day i.If yo...

QLQ 2019-08-15 13:39 评论0 收藏0
Leetcode188. Best Time to Buy and Sell Stock IV

摘要：题目要求有一个整数数组，每一位上的值代表那一天的股票价格。现在假设最多能够进行次交易，问最大的收入是多少思路和代码这里采用了动态编程的思想。题目要求 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...

pingink 2019-08-15 14:20 评论0 收藏0