Concise DP in Java O(k) space O(n) time


  • 0
    G
    public class Solution {
        public int maxProfit(int k, int[] prices) {
            if (prices == null || prices.length == 0 || k <= 0) {
                return 0;
            }
            if (k >= prices.length / 2) {
                int res = 0;
                for (int i = 0; i < prices.length - 1; i++) {
                    if (prices[i + 1] > prices[i]) {
                        res += prices[i + 1] - prices[i];
                    }
                }
                return res;
            }
            int[] hold = new int[k];
            int[] release = new int[k + 1];
            Arrays.fill(hold, Integer.MIN_VALUE);
            for (int i : prices) {
                for (int j = k - 1; j >= 0; j--) {
                    release[j + 1] = Math.max(release[j + 1], hold[j] + i);
                    hold[j] = Math.max(hold[j], release[j] - i);
                }
            }
            return release[k];
        }
    }
    

Log in to reply
 

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