讨论/《初级算法》 - 买卖股票的最佳时机 II/
《初级算法》 - 买卖股票的最佳时机 II

动态规划,在最后一个样例超时了😭😭😭

    class Solution {
    public:
        int dp[30001] = {};
        //dp[i]表示到第i日的最大收益
        //dp[j] = max(dp[i] + (prices[j] - prices[x])) (i < x <= j);
        int maxProfit(vector<int>& prices) {
            dp[0] = 0;    
            int size = prices.size() - 1;
            for (int j = 1; j <= size; j++) {
                int max = 0;
                int max_dp = 0;
                for (int i = 0; i < j; i++) {
                    max_dp = max_dp > dp[i] ? max_dp : dp[i];
                    if (prices[i] >= prices[j]) continue;
                    int deta = dp[i] + prices[j] - prices[i];
                    max = max > deta ? max : deta;
                }
                if (max == 0) {
                    dp[j] = max_dp;
                } else if (max_dp < max){
                    dp[j] = max;
                } else {
                    dp[j] = max_dp;
                }
            }
            return dp[size];
        }
    };
展开全部 170 讨论