买卖股票的最佳时机

121.买卖股票的最佳时机（只能进行一次买入卖出）

记录 历史最低价格

显然，如果我们真的在买卖股票，我们肯定会想：如果我是在历史最低点买的股票就好了！太好了，在题目中，我们只要用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res=0;
        int low=prices[0];
        for(int i=1;i<prices.size();i++){
            res=max(res,prices[i]-low);
            if(prices[i]<low){
                low=prices[i];              
            }          
        }
        return res;
    }
};

差值数组（每天涨了多少或跌了多少）求最大子数组和

122.买卖股票的最佳时机 II（多次买入卖出）

贪心，折线图每个上升段的累加和

贪心算法只能用于计算最大利润，计算的过程并不是实际的交易过程。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res=0;
        for(int i=0;i<prices.size()-1;i++){
            if(prices[i+1]>prices[i])res+=prices[i+1]-prices[i];
        }
        return res;
    }
};

波峰波谷

动态规划，第i天的01两个状态

两次买入卖出

动态规划 dp【N】【4】，第二维分别表示 第一次买入第一次卖出第二次买入第二次卖出，或者两个二维数组 buy【N】【2】，sell【N】【2】

K次买入卖出

动态规划 两个二维数组 buy【N】【K】，sell【N】【K】，或者

dp【N】【K*2】，dp[i][j] 第二维 或许可以滚动数组
0表示买入，1表示卖出，
0 1表示 第一次买入第一次卖出

2 3表示 第二次买入第二次卖出
j+2 /2
第x次买入的编号 =次数x2-2
第x次卖出的编号 =次数x2-1