Best Time to Buy and Sell Stock IV

Best Time to Buy and Sell Stock IV

21%

Accepted

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Have you met this question in a real interview? 

Yes

Example

Given prices = [4,4,6,1,1,4,2,5], and k = 2, return 6.

Note

You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Challenge

O(nk) time.

class Solution {
    /**
     * @param k: An integer
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int k, int[] prices) {
        // write your code here
        int len = prices.length;
        if(k >= len - 1){
            return resolveMax(prices);
        }
        int[] l = new int[k+1];
        int[] g= new int[k+1];
       
        for(int i = 1; i < len; i++){
            int diff = prices[i] - prices[i-1];
            for(int j = k; j >=1; j--){
                l[j] = Math.max(g[j-1] + Math.max(diff, 0), l[j] + diff);
                g[j] = Math.max(g[j], l[j]);
            }
        }
       
        return g[k];
    }
   
    private int resolveMax(int[] prices){
        int res = 0;
        for(int i = 1; i < prices.length; i++){
            res += prices[i] - prices[i-1] > 0 ? prices[i] - prices[i-1] : 0;
        }
        return res;
    }
};