A C++ solution by DP, O(n^2) time O(n) space


  • 0
    L

    By the idea of DP, keep an array maxprofit, such that maxprofit[i] is the max profit using prices[0] to prices[i].

    The recursion is given by maxprofit[i] = max{maxprofit[i - 1], prices[i] - prices[j] + maxprofit[j - 2]: j = 0,1,...,i}, where maxprofit[-1] = maxprofit[-2] = 0.

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

  • 0
    M
    {class Solution {
    public:
    int maxProfit(vector<int>& prices) {
        vector<int>buy(prices.size() + 1, 0);
        vector<int>notbuy(prices.size() + 1, 0);
        // dp[0][i] = max(dp[0][i - 1], dp[1][i - 1]);
        // dp[1][i] = max(dp[0][p] + prices[i] - prices[p + 1], dp[1][p] + prices[i] - prices[p + 2])
        for (int i = 1; i <= prices.size(); i++) {
            notbuy[i] = max(buy[i - 1], notbuy[i - 1]);
            for (int j = i - 1; j >= 0; j--) {
                if (prices[i - 1] > prices[j]) buy[i] = max(buy[i], notbuy[j] + prices[i - 1] - prices[j]);
                if (j < i - 1 && prices[i - 1] > prices[j + 1]) buy[i] = max(buy[i], buy[j] + prices[i - 1] - prices[j + 1]);
            }
        }
        return max(buy[prices.size()], notbuy[prices.size()]);
    }
    

    };
    }

    timeout


  • 0
    J

    The translation for Java:

    public int maxProfit(int[] prices) {
        
        int n = prices.length;
        if(n <= 1) {
            return 0;
        }
    
        int[] maxprofit = new int[n];
        maxprofit[1] = Math.max(prices[1] - prices[0], 0);
    
        for(int i = 2; i < n; i++) {
            int temp = 0;
            for(int j = i; j >= 2; j --) {
                temp = Math.max(temp, maxprofit[j - 2] + prices[i] - prices[j]);
            }
            temp = Math.max(temp, prices[i] - prices[1]);
            temp = Math.max(temp, prices[i] - prices[0]);
            maxprofit[i] = Math.max(temp, maxprofit[i - 1]);
        }
    
        return maxprofit[n - 1];
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.