Say you have an array for which thei_th element is the price of a given stock on day_i.

Design an algorithm to find the maximum profit. You may complete at mostktransactions.

Notice

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

Have you met this question in a real interview?

Yes

Example

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

class Solution {
    /**
     * @param k: An integer
     * @param prices: Given an integer array
     * @return: Maximum profit
     */

    //needs to consider if the number of transaction exceeds number of days over 2 then

    // the max profit is to capture every period that goes upwards == stock II

    //f[i][j] represents the first i day if when i - 1th day stop at state j, the maximum profit earned 
    //total state = 2 * k + 1
    //f[i][j], 0 < j <= 2 * k + 1, have no stock in hand f[i][j] = max{f[i - 1][j], f[i - 1][j - 1] + P[i - 1][i - 2]

    //f[i][j], 1 < j <= 2 * k, have stock in hand (must not the maximum profit), f[i][j] = max {f[i - 1][j - 1], f[i - 1][j] + P[i - 1] - P[i - 2]}

    //ans if max f[i][j]  0 < j <= 2 * k + 1, have no stock in hand
    public int maxProfit(int k, int[] prices) {
        // write your code here
        if (prices == null || prices.length == 0) {
            return 0;
        }




        int n = prices.length;
        int m = 2 * k + 1 + 1;

        if (k >= n / 2) {
            int i;
            int ans = 0;
            for (i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1]) {
                    ans += prices[i] - prices[i - 1];
                }
            }
            return ans;
        }




        int[][] f = new int[2][m];

        //init since there will always been a solution to 0
        int i, j;
        f[0][1] = 0;
        for (j = 2; j < m; j++) {
            f[0][j] = Integer.MIN_VALUE;
        }

        int now = 0;
        int old = 0;
        for (i = 1; i <= n; i ++) {
            old = now;
            now = 1 - now;
            for (j = 1; j < m; j += 2) {
                if (i - 2 < 0) {
                    f[now][j] = f[old][j];
                    continue;
                }

                if (j - 1 < 1 || f[old][j - 1] == Integer.MIN_VALUE) {
                    f[now][j] = f[old][j];
                    continue;
                }

                f[now][j] = Math.max(f[old][j], f[old][j - 1] + prices[i - 1] - prices[i - 2]);
            }

            for (j = 2; j < m - 1; j += 2) {
                if (i - 2 < 0) {
                    f[now][j] = f[i - 1][j - 1];
                    continue;
                }

                if (f[old][j] == Integer.MIN_VALUE) {
                    f[now][j] = f[old][j - 1];
                    continue;
                }

                f[now][j] = Math.max(f[old][j - 1], f[old][j] + prices[i - 1] - prices[i - 2]);
            }

        }
        int ans = 0;
        for (j = 1; j < m; j += 2) {
            ans = Math.max(ans, f[now][j]); 
        }

        return ans;




    }
};