首页 > 试题广场 >

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

[编程题]买卖股票的最好时机(一)
  • 热度指数：171073 时间限制：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]

输出

5

说明

在第3天(股票价格 = 2)的时候买入，在第6天(股票价格 = 7)的时候卖出，最大利润 = 7-2 = 5 ，不能选择在第2天买入，第3天卖出，这样就亏损7了；同时，你也不能在买入前卖出股票。
示例2

输入

[2,4,1]

输出

2
示例3

输入

[3,2,1]

输出

0
算法知识视频讲解
查看答案及解析
添加回答
Python
enjoybaby头像 enjoybaby 
# 一次遍历

class Solution:
    def maxProfit(self , prices ):
        # write code here
        flag = prices[0]
        listA = []
        for j in prices:
            maxSold = j - flag
            if maxSold > 0:
                listA.append(maxSold)
            else:
                listA.append(0)
                flag = j
            
        listA.sort()
        return listA[-1]

发表于 2022-06-10 12:24:13 回复(0)
Python
牛客980779794号头像 牛客980779794号 
class Solution:
    def maxProfit(self , prices ):
        # write code here
        res=[0]*len(prices)
        for i in range(2,len(prices)+1):
            res[-i]=max(res[-i],prices[1-i]+res[1-i]-prices[-i])
        return max(res)
用动态规划的思路倒推每天买入后的最大收益值
发表于 2021-07-12 14:05:34 回复(0)
Python
牛客诶谁头像 牛客诶谁 
class Solution:
    def maxProfit(self , prices ):
        # write code here
        if len(prices) <= 1:
            return 0
        # 存放收益
        lst = []
        lst.append(0)
        for i in range(1, len(prices)):
            # 第i天的最大收益是当前价格减去前i-1天中的最小价格
            lst.append(prices[i] - min(prices[:i]))
        return max(lst)


编辑于 2021-04-25 00:07:10 回复(0)
Python
wengJJ头像 wengJJ
Python
一旦利润变为负，则证明出现新的最低价格
迭代替换 最低价格min_p与最大利润max_m 即可解题 
#
# 
# @param prices int整型一维数组 
# @return int整型
#
class Solution:
    def maxProfit(self , prices ):
        # write code here
        if not prices&nbs***bsp;prices==1:
            return 0
        min_p=prices[0]
        money=0
        max_m=0
        for p in prices:
            money = p-min_p
            if money<0:
                min_p=p
            if money>max_m:
                max_m=money
        return max_money


发表于 2021-04-20 12:51:20 回复(0)
Python
牛客314674748号头像 牛客314674748号
class Solution:
    def maxProfit(self , prices ):
        # write code here
        if prices == []:
            return 0
        MAX = max(prices)
        indexMAX = prices.index(MAX)
        if indexMAX == 0:
            return self.maxProfit(prices[1:])
        elif indexMAX != len(prices)-1:
            return max(MAX-min(prices[:indexMAX]), self.maxProfit(prices[indexMAX+1:]))
        else:
            return MAX-min(prices[:indexMAX])
发表于 2021-04-16 16:01:05 回复(0)
Python
贝贝201903021107589头像 贝贝201903021107589 
# @return int整型
#
class Solution:
    def maxProfit(self , prices ):
        # write code here
        maxval=0
        length=len(prices)
        for i in range(1,length):
            flag=max(prices[i:])-min(prices[:i])
            if flag>maxval:
                maxval=flag
        return maxval

发表于 2021-04-07 20:57:31 回复(0)
Python
猫牛头像 猫牛 
class Solution:
    def maxProfit(self , prices ):
        # write code here
        if not prices:
            return 0
        n = len(prices)
        buy_t = sale_t = 0
        res = prices[sale_t] - prices[buy_t]
        for t in range(n):
            if prices[t] > prices[sale_t]:
                sale_t = t
                res = max(res, prices[sale_t] - prices[buy_t])
            elif prices[buy_t] <= prices[t] <= prices[sale_t]:
                continue
            else:
                buy_t = t
                sale_t = t
                
        return res


发表于 2021-03-12 00:31:53 回复(0)
Python
LHC0512头像 LHC0512
Python 
class Solution:
    def maxProfit(self, prices):
        mini = prices[0]
        profit = 0
        for v in prices:
            if v < mini:
                mini = v
            else:
                profit = max(profit, v - mini)
        return profit


发表于 2021-02-22 17:44:51 回复(0)
Python
DanicaWong头像 DanicaWong 
class Solution:
    def maxProfit(self , prices ):
        # write code here
        result = 0
        for i in range(len(prices)-1):
            if max(prices[i+1:]) - prices[i] > result:
                result = max(prices[i+1:]) - prices[i]
        return result

发表于 2021-02-04 22:40:57 回复(0)
Python
Huster_Finance头像 Huster_Finance
# @param prices int整型一维数组 
# @return int整型
class Solution:
    def maxProfit(self , prices ):
        profit = 0
        minPrice = prices[0]
        for price in prices:
            if price < minPrice:
                minPrice = price
            else:
                profit = max(profit, price - minPrice)
        return profit
发表于 2021-01-20 14:04:46 回复(0)
Python
熬夜写buggg头像 熬夜写buggg 
#动态规划，python
#第i天可能获得的最大利润 = max( 第i-1天可能获得最大利润 ，
#                           第i天prices最高时卖出可能获得最大利润)
class Solution:
    def maxProfit(self , prices ):
        # write code here
        if len(prices) <= 1:
            return 0
        a = [0]*len(prices)
        for i in range(1,len(prices)):
            a[i] = max(a[i-1],prices[i]-min(t for t in prices[:i]))
        return a[-1]

编辑于 2020-09-04 15:18:08 回复(0)
Python
sk8_wt头像 sk8_wt 
class Solution:
    def maxProfit(self , prices ):
        # write code here
        if len(prices)==2:
            return max(prices[1]-prices[0],0)
        num = 0
        out = 0
        # 如果：收益（第0天买入第2天卖出）>收益（第1天买入第2天卖出）
        # 那么一定有：收益（第0天买入第n天卖出）>收益（第1天买入第n天卖出） n>2
        # 所以每增加一天只需比较：收益（第num天买入第n天卖出）与 收益（第n-1天买入第n天卖出）
        # 如果：收益（第num天买入第n天卖出）< 收益（第n-1天买入第n天卖出）
        # 则：num = n-1
        for i in range(1,len(prices)):
            if prices[i]-prices[num]<prices[i]-prices[i-1]:
                num = i-1
                dp = prices[i]-prices[i-1]
            else:
                dp = prices[i]-prices[num]
            out = max(dp,out)
        return out

发表于 2020-08-31 11:11:36 回复(0)
Python
我还是那个胖胖的微微头像 我还是那个胖胖的微微
(python版本）
解释: 

注意你不能在买入股票前卖出股票

输入: [7,1,5,3,6,4]

输出: 5
在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
class Solution:
    def maxProfit(self , prices ):
        # write code here
        """
        :type prices: List[int]
        :rtype: int
        """
        if(len(prices) <= 1):
            return 0
        buy_price = prices[0]
        max_profit = 0
        for i in range(1,len(prices)):
            buy_price = min(buy_price, prices[i])
            max_profit = max(max_profit, prices[i] - buy_price)
        return max_profit
编辑于 2020-08-27 09:34:07 回复(0)
提交观点

问题信息

贪心 动态规划
难度：
14条回答 28807浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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