首页 > 试题广场 >

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

[编程题]买卖股票的最好时机(二)
  • 热度指数：42385 时间限制：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]范围内。
算法知识视频讲解
添加回答
Python 3
杰瑞扁头像 杰瑞扁 
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        n = len(prices)
        #dp[i][0]表示某一天不持股到该天为止的最大收益，dp[i][1]表示某天持股，到该天为止的最大收益
        dp = [[0] * 2 for i in range(n)]
        #第一天不持股，总收益为0
        dp[0][0] = 0
        #第一天持股，总收益为减去该天的股价
        dp[0][1] = -prices[0]
        #遍历后续每天，状态转移
        for i in range(1, n):
            # 第i天不持股有两种情况，第一种昨天就没有买股票，第二种昨天卖出了股票（这里一直保存最大收益，整个过程下来相当于只买了一次）
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
            # 第i天持股有两种情况，第一种昨天就持股，第二种昨天不持股，但是今天买入了（这里相当于寻找最最小值了）
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
        #最后一天不持股，到该天为止的最大收益
        return dp[n - 1][0]

发表于 2022-08-04 16:12:42 回复(2)
Python 3
Vivimore头像 Vivimore 
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        res = 0
        for i in range(1,len(prices)):
            if prices[i] > prices[i-1]:
                res += prices[i] - prices[i-1]
        return res
发表于 2022-05-26 11:58:29 回复(0)
Python 3
牛客356981786号头像 牛客356981786号
u1s1，代码写的稀碎。还想着慢慢调，居然直接通过了。。。 
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        if len(prices) == 0&nbs***bsp;len(prices) == 1:
            return 0
        
        prices.insert(0, float('inf'))
        result = 0
        start = -1
        for i in range(1, len(prices)):
            if i == len(prices)-1:
                if prices[i] >= prices[i-1] and start != -1 and prices[i] > prices[start]:
                    result += prices[i] - prices[start]
                break
            if prices[i] < prices[i-1] and prices[i] <= prices[i+1]:
                start = i
            if prices[i] >= prices[i-1] and prices[i] > prices[i+1]:
                if start != -1:
                    result += prices[i] - prices[start]
                start = -1
        return result


发表于 2022-03-18 00:46:30 回复(0)
Python 3
Virtual~头像 Virtual~
Python 贪心解法： 
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        res = 0
        pivot = 0
        index = 1
        while index < len(prices):
            if prices[index] > prices[pivot]:
                while index + 1 < len(prices) and prices[index+1] > prices[index]: 
                    index += 1
                res += (prices[index] - prices[pivot])
                pivot = index + 1
                index = index + 2
            else:
                index += 1
                pivot += 1
        
        return res


发表于 2022-03-10 23:31:22 回复(1)
Python 3
Joy_9头像 Joy_9 
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        if not prices:
            return 0
        dp=[0]*len(prices)
        min_price=prices[0]
        res=[]
        for i in range(1,len(prices)):
            min_price=min(prices[i],min_price)
            if dp[i-1]<prices[i]-min_price:
                res.append(prices[i]-min_price)
                min_price=prices[i]
                dp[i]=0
            else:
                dp[i]=dp[i-1]
        return sum(res)
                

发表于 2022-01-21 07:30:53 回复(0)
Python 3
香草街头像 香草街
为了技术而写题，本来一个for循环，时间n，空间1的东西，非要搞出那么多花里胡哨
发表于 2021-11-06 00:53:27 回复(0)
Python 3
又要找工作了头像 又要找工作了 
class Solution:
    def maxProfit(self , prices ):
        # write code here
        if not prices:
            return 0
        maxp = 0
        minp = prices[0]
        for p in range(1, len(prices)):
            if prices[p] - prices[p-1] > 0:
                maxp += prices[p] - prices[p-1]
        return maxp

发表于 2021-10-25 19:05:10 回复(0)
Python 3
刺猬她很瘦头像 刺猬她很瘦 
class Solution:
    def maxProfit(self , prices ):
        # write code here
        max = 0 
        for i in range(len(prices)-1 ) :
            if prices[i] <= prices[i+1] :
                tmp = prices[i+1] -prices[i]
                max += tmp
        return max

发表于 2021-08-26 09:54:25 回复(0)
Python 3
牛客152785677号头像 牛客152785677号 
class Solution:
    def maxProfit(self , prices ):
        max_out = 0
        for i in range(len(prices)-1):
            max_out += max(prices[i+1] - prices[i],0)
        return max_out

发表于 2021-08-13 22:33:27 回复(0)
Python 3
蒙太奇在秋天头像 蒙太奇在秋天
极小值买进，极大值卖出。注意两个一样大和一样小的值的取舍。 
class Solution:
    def maxProfit(self , prices ):
        # write code here
        takein = 0
        if prices == []:
            return 0
        if len(prices) == 1:
            return 0
        if prices[1]>prices[0]:
            takein = -prices[0]
        i = 1
        while i < len(prices)-1:
            if (prices[i]<=prices[i-1])&(prices[i]<prices[i+1]):
                takein -= prices[i]
            if (prices[i]>prices[i-1])&(prices[i]>=prices[i+1]):
                takein += prices[i]
            i += 1
        if prices[-1]>prices[-2]:
            takein += prices[-1]
        return takein


发表于 2021-08-05 09:18:56 回复(0)
Python 3
Wayne_2022头像 Wayne_2022
class Solution:
    def maxProfit(self , prices ):
        maxfit=0
        s1=prices[0]
        for j in range(1,len(prices)):
            if prices[j] >s1:
                maxfit += prices[j] - s1
                s1 = prices[j]
            else:
                s1=prices[j]
        return maxfit
发表于 2021-07-22 17:28:23 回复(0)
提交观点

问题信息

贪心 动态规划
难度：
12条回答 9503浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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