Leetcode 121. Best Time to Buy and Sell Stock (python+cpp）

题目

这题挺简单的，但是为了记录的完整性，还是写一下。

解法1：brutal force （TLE）

两边循环找出最大值，最na?ve的方法
python代码如下：

class Solution:def maxProfit(self, prices: List[int]) -> int:_max = 0for i in range(len(prices)):for j in range(i+1,len(prices)):_max = max(_max,prices[j]-prices[i])return _max

解法2：single pass

保存两个值，一个track到现在为止出现过的最小值，一个track最大的profit，然后每次先更新最大的profit，然后更新最小值
python代码如下：

class Solution:def maxProfit(self, prices: List[int]) -> int:_min = float('inf')_max = 0for price in prices:_max = max(_max,price-_min)_min = min(_min,price)return _max

C++代码如下：

class Solution {
    
public:int maxProfit(vector<int>& prices) {
    int curr_max = 0, curr_min = INT_MAX;for (auto price:prices){
    curr_max = max(curr_max,price-curr_min);curr_min = min(curr_min,price);}return curr_max;}
};

我比较疑惑的是这个题目的tag是动态规划，这题我是看不出来为啥是个动态规划