【动态规划】--买卖股票的最佳时机

​
​

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。各位小伙伴，如果您：
想系统/深入学习某技术知识点…
一个人摸索学习很难坚持，想组团高效学习…
想写博客但无从下手，急需写作干货注入能量…
热爱写作，愿意让自己成为更好的人…
PS：恰好也有学习经典算法的计划，顺便mark一下～
…

题目：

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

1
2
3
4
5
6

代码：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # total=0
        # for i in range(len(prices)-1 ):
        #     if prices[i+1]>prices[i]:
        #         total=total+prices[i+1]-prices[i]
        # return total
        r = 0
        min_price = float('inf')  # float('inf')表示负无穷
        for price in prices:
            min_price = min(min_price, price)  # 截止到当前的最低价（买入价）
            r = max(r, price - min_price)  # 截止到目前的最高利润
        return r


    def best(self,prices: List[int])->int:
        return sum([prices[i+1]-prices[i] for i in range(len(prices)-1) if prices[i+1]>prices[i]])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

学习日记

**
1，学习知识点

• 时间复杂度：O(n)，遍历了一遍数组。
• 空间复杂度：O(1)，使用了有限的变量。

​