首页 > 试题广场 >

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

[编程题]买卖股票的最好时机(三)

热度指数：37571 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
1. 你最多可以对该股票有两笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票
2. 如果不能获取收益，请返回0
3. 假设买入卖出均无手续费

数据范围： $1 \le n \le 10^5$ ，股票的价格满足 $1 \le val\le 10^4$

要求: 空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

[8,9,3,5,1,3]

输出

说明

第三天(股票价格=3)买进，第四天(股票价格=5)卖出，收益为2
第五天(股票价格=1)买进，第六天(股票价格=3)卖出，收益为2
总收益为4。

示例2

输入

[9,8,4,1]

输出

示例3

输入

[1,2,8,3,8]

输出

说明

第一笔股票交易在第一天买进，第三天卖出；第二笔股票交易在第四天买进，第五天卖出；总收益为12。
因最多只可以同时持有一只股票，所以不能在第一天进行第一笔股票交易的买进操作，又在第二天进行第二笔股票交易的买进操作（此时第一笔股票交易还没卖出），最后两笔股票交易同时在第三天卖出，也即以上操作不满足题目要求。

备注:

总天数不大于200000。保证股票每一天的价格在[1,100]范围内。

算法知识视频讲解

牛客题解官

发表于 2022-04-22 12:55:35

精华题解题目主要信息: 给出一个数组表示连续多日的股票价格你可以选择在某一天买入股票，在另一天卖出股票，可以最多买入两次卖出两次，但是第二次买入必须在第一次卖出后，且每天只能进行一次操作假设买卖没有手续费，问最高收益是多少，即卖出的价格减去买入的价格，如果没有利润需要返回0 举一反三：学习完本题的展开全文

牛客516598323号

发表于 2020-09-21 20:32:24

思想：用一个flag把区间分为两部分，找到两部分各自的谷（买入）和峰（卖出）。从0到n移动flag遍历数组。注意：这里代码并没有flag，只不过分两次把flag的两部分遍历找了出来。参考答案： class Solution { public: /** * 代码中的类名、方法名、参数名已经指定展开全文

deamn

发表于 2022-05-06 14:36:21

对于股票问题我们只需要得到所有的状态转移方程即可由于题目要求只能交易两次我们可以得到buy1，即第一次购买股票，sell1，第一次出售股票，buy2，第一次交易完成后第二次购买股票，sell2，第二次出售股票 class Solution: def maxProfit(self , pr 展开全文

小洋芋热爱NLP

发表于 2021-01-30 23:31:04

- 1、题目描述： - 2、题目链接：https://www.nowcoder.com/practice/4892d3ff304a4880b7a89ba01f48daf9?tpId=117&&tqId=35490&rp=1&ru=/ta/job-code-high& 展开全文

棒棒糖🍭201906101800876

发表于 2021-10-13 09:13:43

NC135. 股票交易的最大收益（二）描述假定你知道某只股票每一天价格的变动。你最多可以同时持有一只股票。但你最多只能进行两次交易（一次买进和一次卖出记为一次交易。买进和卖出均无手续费）。请设计一个函数，计算你所能获得的最大收益。 1. 动态规划跟NC134的分析思路一样，第n天的最大收益展开全文

xqxls

发表于 2021-07-18 18:29:13

题意整理已知股票每一天的价格波动最多持有一只股，也就是买入时，必须卖出之前持有的股最多交易两次，求最大收益方法一（动态规划） 1.解题思路本题的难点在于交易次数进行了限定，可以多开一维空间来存储交易次数。所以可以用三维dp来求解。状态定义：第一维表示交易天数，第二维表示交易次数，第展开全文

JaxonSuzy

发表于 2020-12-13 14:50:39

这题的难点在于如何处理第二次交易。我首先从后往前遍历数组，f[i]表示从i点开始到结尾进行的一次交易的最大收益。第二次交易处理完了，就可以用常见的方法进行类似一次交易，每次比较时再加上对应的f[i+1]即可。 res = Math.max(res,prices[i]-min + f[i+1] 展开全文

有名

发表于 2021-08-01 17:17:25

描述假定你知道某只股票每一天价格的变动。你最多可以同时持有一只股票。但你最多只能进行两次交易（一次买进和一次卖出记为一次交易。买进和卖出均无手续费）。请设计一个函数，计算你所能获得的最大收益。方法一思路正反两次循环遍历题目明确指出最多可以进行两次交易，且这两次交易在时间上是有先后次展开全文

LifelongCode

发表于 2021-01-12 16:52:46

解法1：贪心要计算买卖两次的收益，只需要找到一天k，使得f(0, k) + f(k + 1, n - 1)最大即可;运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。case通过率为0.00% public int maxProfit (int[] price 展开全文

JZZZZZZZZZZZ

发表于 2020-12-26 20:21:32

该题是典型的dp，首先常规思维来说，我们需要一个n x prices.length大小的array。dp[k][i]就代表在到i个价格为止进行了k次交易获得的收益。每次在计算当前dp[k][i]的时候有两种情况。当前价格没有交易发生，从上一个cell取值，即dp[k][i-1] 发生交易，从j 展开全文

姐姐的遮阳伞

发表于 2022-03-23 16:12:17

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 两次交易所能获得的最大收益 * @param prices int整型一维数组展开全文

问题信息

动态规划

难度：

73条回答 610收藏 7531浏览

通过挑战的用户

搞技术的菜嘚嘚

2022-09-16 17:45:25
不停20190...

2022-09-16 15:26:50
下曲未完

2022-09-16 12:40:37
牛客35637...

2022-09-16 11:49:01
zzkkss

2022-09-16 11:17:19

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

输入

输出

说明

输入

输出

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题