题解 | #买卖股票的最好时机(一)#

买卖股票的最好时机(一)：最直观的想法是，动态规划。交易一次*是否持股一共有两种状态，分别使用dp[i][0]表示第i天持股，使用dp[i][1]表示第i天不持股，然后根据常识对第一天的两种状态进行初始化，接着从第二天开始遍历，分别更新递推公式，其中第i天持股可能是第i-1天就持股或者第i-1天不持股而第i天买入，由于只能买卖一次，故此处为0而不是dp[i-1][1]，第i-1天不持股可能是第i-1天就不持股或者第i-1天持股而第i-1天卖出，最后返回第n-1天不持股状态即为最大收益。

    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        // 处理空数组
        if(n==0||n==1)
            return 0;
        // dp[i][0]表示第i天持股 dp[i][1]表示第i天不持股
        vector<vector<int>> dp(n,vector<int>(2,0));
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        for(int i=1;i<n;i++)
        {
            // 第i天持股可能是第i-1天就持股或者第i-1天不持股而第i天买入
            // 由于只能买卖一次 故此处是0而不是dp[i-1][1]
            dp[i][0]=max(dp[i-1][0],0-prices[i]);
            // 第i天不持股可能是第i-1天就不持股或者第i-1天持股而第i天卖出
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }
        // 最大的即是第n-1天不持股
        return dp[n-1][1];
    }