剑指 Offer 63. 股票的最大利润（中等）

题目：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;      //要考虑数组为空的情况
        vector<vector<int>> dp(prices.size(), vector<int>(2, 0));      //确定动态数组大小和下表含义dp[i][j]：第i天j状态下的利润。其中：j=0代表不持有股票，j=1代表持有股票
        dp[0][0]=0;      //初始化动态数组，第一天不持有股票和第一天买入股票
        dp[0][1]=-prices[0];
        for(int i=1;i<=prices.size()-1;i++){
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]);      //不持有股票两种情况：1.前一天就不持有 2.今天刚卖出
            dp[i][1] = max(dp[i-1][1], -prices[i]);      //持有股票两种情况：1.前一天就持有 2.今天刚买入
        }
        return dp[prices.size()-1][0];      //获取最大利润一定是不持有股票的状态
    }
};