难度：简单

题目内容：

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

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

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

题解：

噢又回到了简单题真是太好了 (x)
这个题我的想法是先求微分，然后就最大连续序列和
然后突然想起了当年我瞬间想到的在线处理应该是求最大子列和哈哈哈哈

import numpy as np
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        r = 0
        dp = list(np.diff(prices))
        s = 0
        maxs = 0
        for i in range(len(dp)):
            s += dp[i]
            if s > maxs:
                maxs = s
            if s < 0:
                s = 0
        return int(maxs)

然后发现我六个月前做过这个。。。

不过时间和内存不太理想吼
还是来看下官方的答案吧，同样是一次遍历，不过不用像我这样求微分
果然是我想歪了
不断的更新最低点，然后用当天的价格计算利润对比更新最大利润
我当时为什么没有考虑直接这么算呢，是因为我担心比如说出现5，10，1，2
这样最低点前已经完成交易才能获得更大利润的情况
但是如果不断更新最低点的话，就是10-5 = 5，先把这个利润更新进来了，就么的问题了。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        inf = int(1e9)
        minprice = inf
        maxprofit = 0
        for price in prices:
            maxprofit = max(price - minprice, maxprofit)
            minprice = min(price, minprice)
        return maxprofit

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-by-leetcode-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

果然比我这个快不少
试试去掉inf，直接把minprice的初始值设为minprice = prices[0] if prices else 0
emmm好像占用并没有什么变化

好奇大佬们的内存怎么用的那么少。