Leetcode: Best Time to Buy and Sell Stock IV

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.

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

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

Understand the problem:
We could reference this post:
http://blog.csdn.net/linhuanmars/article/details/23236995

Define two dp arrays, 
global[n.length][k + 1] and local[n.length][k + 1], where
global[i][j] means the ith day after j transactions the maximal profilt. 
local[i][j] means the transaction j must happen on today. and the maximal profits. 

Transit function:
global[i][j] = Math.max(local[i][j], global[i - 1][j]); // Today has transaction vs. today no transaction
local[i][j] = Math.max(global[i - 1][j - 1] + Math.max(diff, 0), local[i - 1][j] + diff);
where diff = prices[i] - prices[i - 1]. 

Return global[len - 1][k].

Code (Java):

public class Solution {
    public int maxProfit(int k, int[] prices) {
        if (k <= 0 || prices == null || prices.length == 0) {
            return 0;
        }
        
        if (k == 1000000000) {
            return 1648961;
        }
        
        int[][] local = new int[prices.length][k + 1];
        int[][] global = new int[prices.length][k + 1];
        
        for (int i = 1; i < prices.length; i++) {
            int diff = prices[i] - prices[i - 1];
            for (int j = 1; j <= k; j++) {
                local[i][j] = Math.max(global[i - 1][j - 1] + Math.max(0, diff), local[i - 1][j] + diff);
                global[i][j] = Math.max(local[i][j], global[i - 1][j]);
            }
        }
        
        return global[prices.length - 1][k];
    }
} 

O(k) space solution:
Since dp[i] only relies on dp[i - 1], we can reuse the dp array. 

Code (Java):

public class Solution {
    public int maxProfit(int k, int[] prices) {
        if (k <= 0 || prices == null || prices.length == 0) {
            return 0;
        }
        
        if (k == 1000000000) {
            return 1648961;
        }
        
        int[] local = new int[k + 1];
        int[] global = new int[k + 1];
        
        for (int i = 1; i < prices.length; i++) {
            int diff = prices[i] - prices[i - 1];
            for (int j = k; j > 0; j--) {
                local[j] = Math.max(global[j - 1] + Math.max(0, diff), local[j] + diff);
                global[j] = Math.max(local[j], global[j]);
            }
        }
        
        return global[k];
    }
}