leetcode hot100刷题日记——19.买卖股票的最佳时机
解答：
class Solution {
public:int maxProfit(vector<int>& prices) {//思路:买股票的时候希望自己在最低点买入，最高点卖出，但是有卖出点要在买入点后面的时间限制//而遍历，自然而然有“时间限制”//所以在一次遍历过程中，我们把每天都看成考虑要不要卖出去，假设自己之前是在最低点买入//更新最低价格//检查当前能不能得到最高利润，即maxx=max(maxx,prices[i]-minn);int minn=1e9;int maxx=0;int n=prices.size();if(n==1){return 0;}for(int i=0;i<n;i++){minn=min(minn,prices[i]);maxx=max(maxx,prices[i]-minn);}return maxx;}
};
时间复杂度：O(N)
空间复杂度：O(1)
看到题解说这也是一种动态规划的思想，我们来捋一下：
对于第i天，
- 我们如果在前i-1天已经完成了一轮买卖操作，则第i天不能做任何操作，问题转化为dp[i-1]
- 如果我们在前i-1天只是做了买入，在第i天卖出，那么在第0到第i天，进行一轮买卖操作，在这种情况下，卖出的价格一定是prices[i]，那么买入价格一定是前i-1天中的最小值，即minn=min(prices[0],……prices[i-1])，收益就是prices[i]-minn
而要使收益最大，dp[i]=max(dp[i-1],prices[i]-minn)