我要招人

去企业版

首页 > 试题广场 >

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

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

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

假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天

2.如果不能获取到任何利润，请返回0

3.假设买入卖出均无手续费

数据范围： $0 \le n \le 10^5 , 0 \le val \le 10^4$

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

示例1

输入

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

输出

说明

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

示例2

输入

[2,4,1]

输出

示例3

输入

[3,2,1]

输出

算法知识视频讲解

Python

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号

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

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号

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

# @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

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

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

# @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

#动态规划，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

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)