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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        if(prices.size()<2){
            
            return 0;
        }
        if(prices.size()==2&&prices[1]-prices[0]<0){
                 
            return 0;
        }
        vector<int> dp(prices.size()+1);
        dp[0]=0;
        dp[1]=prices[1]-prices[0];
        int min_price=prices[0];
        for(int i=1;i<prices.size();i++){
            dp[i+1]=max(dp[i],prices[i]-min_price);
            min_price=min(min_price,prices[i]);
        }
        return dp[prices.size()];

        
    }
};

动态规划：假设第t天时，最大利润是m,第t+1天呢？我们需要考虑这多出来的一天是否需要操作，如果不需要操作那么最大利润还是m，如果需要操作，那么必然是t+1天卖出，那么怎么样使得利润最大，就是在1-t天内找一个最低min_price的买入。所以构建dp(prices.size+1); 第一天不能完成买卖各一次。第二天可以买卖一次，就是第一天买，第二天卖。就是第二天的价格-第一天的min_price所以min_price初始按第一天的算 int min_price=prices[0]; 那么第三天就是判断仍然保持第二天的操作还是第三天卖出 dp[i+1]=max(dp[i],prices[i]-min_price); ，在第1-2天选最小的买入。所以需要同步维持一个最小值min_prices. min_price=min(min_price,prices[i]); 按这个逻辑进行下去就可以找到整个t天的最大利润。此外有可能只有一天吗，那就是利润为0，当只有两天时，并且操作可以完成是亏本的，按题目所给条件，也是返回0；