Best Time to Buy and Sell Stock 4

题目地址：
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/#/description

题目：

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

解题思路：
这道题首先要清楚k的范围。当k >= len / 2的时候，相当于可以交易as many as you can。当k < len / 2的时候就要用动态规划来解决了。建立二维数组，i是row，为交易次数，j是prices的index。dp[i][j]表示selling at prices j或者selling at prices j之前，并且进行了i次交易的最大利润。localMax表示buying at prices j或者buying before prices j之前的最大利润。


代码：

public int maxProfit(int k, int[] prices) {
    if(prices == null || prices.length <= 1){
        return 0;
    }
    int len = prices.length;
    if(k >= len / 2){
        int max = 0;
        for(int i = 1; i <= len - 1; i++){
            max += Math.max(0, prices[i] - prices[i - 1]);
        }
        return max;
    }
    int[][] dp = new int[k + 1][len];
    for(int i = 1; i <= k; i++){
        int max = -prices[0];
        for(int j = 1; j <= len - 1; j++){
            dp[i][j] = Math.max(dp[i][j - 1], max + prices[j]);
            max = Math.max(max, dp[i - 1][j] - prices[j]);
        }
    }
    return dp[k][len - 1];
}