Java DP solution


  • 0
    D
    public class Solution {
        public int maxProfit(int k, int[] prices) {
            if (prices == null || prices.length < 2) {
                return 0;
            }
            int n = prices.length;
            int ret = 0;
            if (k >= n / 2) {
                for (int i = 1; i < n; i++) {
                    if (prices[i] > prices[i - 1]) {
                        ret += prices[i] - prices[i - 1];
                    }
                }
                return ret;
            }
            int[][] dp = new int[k + 1][n];
            for (int kk = 1; kk <= k; kk++) {
                int max = Integer.MIN_VALUE;
                for (int i = 1; i < n; i++) {
                    max = Math.max(max, (i > 1 ? dp[kk - 1][i - 2] : 0) - prices[i - 1]);
                    dp[kk][i] = Math.max(dp[kk][i - 1], prices[i] + max);
                }
            }
            return dp[k][n - 1];
        }
    }
    

Log in to reply
 

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