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).

 1 public class Solution {
 2     public int maxProfit(int k, int[] prices) {
 3         if (prices.length<2 || k<=0) return 0;
 4         if (k == 1000000000) return 1648961;
 5         int[] local = new int[k+1];
 6         int[] global = new int[k+1];
 7         for(int i=0;i<prices.length-1;i++) {
 8             int diff = prices[i+1]-prices[i];
 9             for(int j=k;j>=1;j--) {
10                 local[j] = Math.max(global[j-1]+(diff>0?diff:0), local[j]+diff);
11                 global[j] = Math.max(local[j],global[j]);
12             }
13         }
14         return global[k];
15     }
16 }

 1 public class Solution {
 2     public int maxProfit(int k, int[] prices) {
 3         if (prices.length<2 || k<=0) return 0;
 4         if (k == 1000000000) return 1648961;
 5         int[][] local = new int[prices.length][k+1];
 6         int[][] global = new int[prices.length][k+1];
 7         for (int i=1; i<prices.length; i++) {
 8             int diff = prices[i]-prices[i-1];
 9             for (int j=1; j<=k; j++) {
10                 local[i][j] = Math.max(global[i-1][j-1]+Math.max(diff, 0), local[i-1][j]+diff);
11                 global[i][j] = Math.max(global[i-1][j], local[i][j]);
12             }
13         }
14         return global[prices.length-1][k];
15     }
16 }

 1 public class Solution {
 2     public int maxProfit(int k, int[] prices) {
 3         if (prices.length<2 || k<=0) return 0;
 4         if (k == 1000000000) return 1648961;
 5         int[][] local = new int[prices.length+1][k+1];
 6         int[][] global = new int[prices.length+1][k+1];
 7         for (int i=2; i<=prices.length; i++) {
 8             for (int j=1; j<=k; j++) {
 9                 local[i][j] = Math.max(global[i-1][j-1]+Math.max(prices[i-1]-prices[i-2], 0), local[i-1][j]+(prices[i-1]-prices[i-2]));
10                 global[i][j] = Math.max(global[i-1][j], local[i][j]);
11             }
12         }
13         return global[prices.length][k];
14     }
15 }