Simple java solution


  • 0
    H
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int[] dp = new int[prices.length]; 
        int max = 0;
        for (int i = 1; i < prices.length; i++) { // i sell
            for (int j = i - 1; j >= 0; j--) { // j buy
                if (j < 2) {
                    dp[i] = Math.max(prices[i] - prices[j], dp[i]);
                } else {
                    dp[i] = Math.max(dp[j - 2] + prices[i] - prices[j], dp[i]);
                }
                dp[i] = (j == 0) ? dp[i] : Math.max(dp[i - 1], dp[i]);
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

Log in to reply
 

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