首页 > 试题广场 >

买卖股票的最好时机(二)

[编程题]买卖股票的最好时机(二)
  • 热度指数：42510 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
1. 你可以多次买卖该只股票，但是再次购买前必须卖出之前的股票
2. 如果不能获取收益，请返回0
3. 假设买入卖出均无手续费

数据范围： ，
要求：空间复杂度 ，时间复杂度
进阶：空间复杂度 ，时间复杂度
示例1

输入

[8,9,2,5,4,7,1]

输出

7

说明

在第1天(股票价格=8)买入，第2天(股票价格=9)卖出，获利9-8=1
在第3天(股票价格=2)买入，第4天(股票价格=5)卖出，获利5-2=3
在第5天(股票价格=4)买入，第6天(股票价格=7)卖出，获利7-4=3
总获利1+3+3=7，返回7
示例2

输入

[5,4,3,2,1]

输出

0

说明

由于每天股票都在跌，因此不进行任何交易最优。最大收益为0。
示例3

输入

[1,2,3,4,5]

输出

4

说明

第一天买进，最后一天卖出最优。中间的当天买进当天卖出不影响最终结果。最大收益为4。

备注:
总天数不大于200000。保证股票每一天的价格在[1,100]范围内。
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2022-04-22 12:54:58
精华题解 题目主要信息： 给出一个数组表示连续多日的股票价格 你可以选择在某一天买入股票，在另一天卖出股票，买卖可以有多次机会，但是同一天只能买或者只能卖 假设买卖没有手续费，问最高收益是多少，即卖出的价格减去买入的价格，如果没有利润需要返回0 举一反三： 学习完本题的思路你可以解决如下题目： BM78. 展开全文
去ta的博客 赞 (8) 回复(2) 收起
头像 数据结构和算法
发表于 2021-03-21 13:04:12
1，动态规划解决 定义dp[i][0]表示第i+1天交易完之后手里没有股票的最大利润，dp[i][1]表示第i+1天交易完之后手里持有股票的最大利润。 当天交易完之后手里没有股票可能有两种情况，一种是当天没有进行任何交易，又因为当天手里没有股票，所以当天没有股票的利润只能取前一天手里没有股票的利润 展开全文
去ta的博客 赞 (40) 回复(2) 收起
头像 王清楚
发表于 2020-12-15 12:33:19
例 ：1 5 8 4 2 3 6 4 10 7 3 2 1 6对于这个样例来说，最优的交易应该是：第1天买，第3天卖第5天买，第7天卖第8天买，第10天卖第13天买，第14天卖我们再观察可以发现，其实可以简化成，只要是两天之间是上涨的，那我们就要这一段的收益。 c++ class Solution 展开全文
去ta的博客 赞 (36) 回复(0) 收起
头像 超级码力233
发表于 2020-11-26 19:11:50
股票交易的最大收益 题目链接 Solution 已经知道每一天股票的价格，可以无限次交易，每天只能进行一次，询问最大收益。这类问题可以动态规划解决。设表示到第i天的时候，最大收益是多少。首先可以直接从上一天继承过来，即。其次，如果在第i天卖出，那么需要选择一天买入，设第j天买入，则如果第i天买入的话 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 Jason1995
发表于 2020-12-10 17:12:12
数组后一个减去前一个，为正数就加起来 public class Solution { public int maxProfit (int[] prices) { int sum = 0; for (int i = 1; i < prices.length 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 小洋芋热爱NLP
发表于 2021-02-05 18:54:58
- 1、题目描述： - 2、题目链接： https://www.nowcoder.com/practice/9e5e3c2603064829b0a0bbfca10594e9?tpId=117&tqId=37846&rp=1&ru=%2Factivity%2Foj&q 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 感谢信收集器一号
发表于 2022-11-16 13:13:44
动态规划基本思想
去ta的博客 赞 (1) 回复(0) 收起
头像 大哥们不要卷我
发表于 2022-02-28 15:17:03
本题首先要清楚两点： 只有一只股票！ 当前只有买股票或者买股票的操作 想获得利润至少要两天为一个交易单元 这道题目可能我们只会想，选一个低的买入，在选个高的卖，在选一个低的买入.....循环反复。 如果想到其实最终利润是可以分解的，那么本题就很容易了！ 如何分解呢？ 假如第0天买入，第3天卖出，那么 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛一霸
发表于 2021-07-21 22:52:31
题目：股票无限次交易 描述：假定你知道某只股票每一天价格的变动。 你最多可以同时持有一只股票。但你可以无限次的交易（买进和卖出均无手续费）。 请设计一个函数，计算你所能获得的最大收益。 示例1：输入：[5,4,3,2,1]，返回值：0 说明：由于每天股票都在跌，因此不进行任何交易最优。最大收益为0。 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Virtual~
发表于 2022-03-10 23:55:39
Python 动态规划 class Solution:     def maxProfit(self , prices: List[int]) -> int:   展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Double_冰
发表于 2022-05-18 10:07:32
/* 当天持股/不持股所能获得的最大利益 当天持股 = max（前一天持股，前一天不持股 - 今天买入所花费） dp[i][0] = max(dp[i-1][0],dp[i-1][1] - prices[i]); 当天不 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

贪心 动态规划
难度：
99条回答 9757浏览

热门推荐

通过挑战的用户

查看代码

相关试题

买卖股票的最好时机(二)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号