LeetCode 188 - Best Time to Buy and Sell Stock IV


LeetCode 121 - Best Time to Buy and Sell Stock
LeetCode - Best Time to Buy and Sell Stock II
LeetCode - Best Time to Buy and Sell Stock III
LeetCode 188 - Best Time to Buy and Sell Stock IV
Leetcode 309 - Best Time to Buy and Sell Stock with Cooldown
LeetCode 714 - Best Time to Buy and Sell Stock with Transaction Fee

The Code Sniper: 188. Best Time to Buy and Sell Stock IV Leetcode Java
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).Think about the possible input, may use different algorithm.solution: in this case, if k>len/2.

X.  O(KN^2)
https://www.hrwhisper.me/leetcode-best-time-to-buy-and-sell-stock-i-ii-iii-iv/
设dp[i][x]为第i天第x次交易的最大利润，则容易写出dp方程：
  • dp[i][x] = max(dp[i-1][x] , dp[j][x – 1] + prices[i] – prices[j])  0 <= j < i
  • 上面的状态转移方程第一项为第i天不进行交易，第二项为枚举j 从0~i-1，第j天买入，第i天卖出
注意当k >= len(prices) / 2的时候，说明相当于无限次交易，和第122题Best Time to Buy and Sell Stock II 一样。
上面的复杂度为O(kn^2)代码如下:
    int maxProfit(int k, vector<int>& prices) {
        if(prices.empty()) return 0;
        int ans = 0;
        if(k >= prices.size() / 2){
            for(int i = 1; i < prices.size(); ++i){
                if(prices[i] > prices[i - 1])
                    ans += prices[i] - prices[i - 1];
            }
            return ans;
        }
        vector<vector<int>> dp(prices.size(), vector<int>(k + 1, 0));
        for(int x = 1; x <= k; ++x){
            for(int i = 1; i < prices.size(); ++i){
                dp[i][x] = dp[i - 1][x]; // 不做交易
                for(int j = 0; j < i; ++j){
                    dp[i][x] = max(dp[i][x], dp[j][x - 1] + prices[i] - prices[j]);
                }
            }
            ans = max(ans, dp[prices.size() - 1][x]);
        }
        return ans;
    }

    static int maxProfit(int[] price, 
                         int n, 
                         int k)
    {
          
        // table to store results
        // of subproblems
        // profit[t][i] stores 
        // maximum profit using 
        // atmost t transactions up
        // to day i (including day i)
        int[][] profit = new int[k + 1][n + 1];
  
        // For day 0, you can't 
        // earn money irrespective
        // of how many times you trade
        for (int i = 0; i <= k; i++)
            profit[i][0] = 0;
  
        // profit is 0 if we don't
        // do any transation
        // (i.e. k =0)
        for (int j = 0; j <= n; j++)
            profit[0][j] = 0;
  
        // fill the table in 
        // bottom-up fashion
        for (int i = 1; i <= k; i++) 
        {
            for (int j = 1; j < n; j++)
            {
                int max_so_far = 0;
  
                for (int m = 0; m < j; m++)
                max_so_far = Math.max(max_so_far, price[j] -
                             price[m] + profit[i - 1][m]);
  
                profit[i][j] = Math.max(profit[i] [j - 1], 
                                              max_so_far);
            }
        }
  
        return profit[k][n - 1];
    }

X. O(NK)
https://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-most-k-times/
Let profit[t][i] represent maximum profit using at most t transactions up to day i (including day i). Then the relation is:
profit[t][i] = max(profit[t][i-1], max(price[i] – price[j] + profit[t-1][j]))
          for all j in range [0, i-1]
profit[t][i] will be maximum of –
  1. profit[t][i-1] which represents not doing any transaction on the ith day.
  2. Maximum profit gained by selling on ith day. In order to sell shares on ith day, we need to purchase it on any one of [0, i – 1] days. If we buy shares on jth day and sell it on ith day, max profit will be price[i] – price[j] + profit[t-1][j] where j varies from 0 to i-1. Here profit[t-1][j] is best we could have done with one less transaction till jth day.
The above solution has time complexity of O(k.n2). It can be reduced if we are able to calculate maximum profit gained by selling shares on ith day in constant time.
profit[t][i] = max(profit [t][i-1], max(price[i] – price[j] + profit[t-1][j]))
                            for all j in range [0, i-1]
If we carefully notice,
max(price[i] – price[j] + profit[t-1][j])
for all j in range [0, i-1]
can be rewritten as,
= price[i] + max(profit[t-1][j] – price[j])
for all j in range [0, i-1]
= price[i] + max(prevDiff, profit[t-1][i-1] – price[i-1])
where prevDiff is max(profit[t-1][j] – price[j])
for all j in range [0, i-2]
So, if we have already calculated max(profit[t-1][j] – price[j]) for all j in range [0, i-2], we can calculate it for j = i – 1 in constant time. In other words, we don’t have to look back in range [0, i-1] anymore to find out best day to buy. We can determine that in constant time using below revised relation.
profit[t][i] = max(profit[t][i-1], price[i] + max(prevDiff, profit [t-1][i-1] – price[i-1])
where prevDiff is max(profit[t-1][j] – price[j]) for all j in range [0, i-2]
Time complexity of above solution is O(kn) and space complexity is O(nk). Space complexity can further be reduced to O(n) as we uses the result from last transaction. 
int maxProfit(int price[], int n, int k)
{
    // table to store results of subproblems
    // profit[t][i] stores maximum profit using atmost
    // t transactions up to day i (including day i)
    int profit[k+1][n+1];
    // For day 0, you can't earn money
    // irrespective of how many times you trade
    for (int i = 0; i <= k; i++)
        profit[i][0] = 0;
    // profit is 0 if we don't do any transation
    // (i.e. k =0)
    for (int j= 0; j <= n; j++)
        profit[0][j] = 0;
    // fill the table in bottom-up fashion
    for (int i = 1; i <= k; i++)
    {
        int prevDiff = INT_MIN;
        for (int j = 1; j < n; j++)
        {
            prevDiff = max(prevDiff,
                           profit[i-1][j-1] - price[j-1]);
            profit[i][j] = max(profit[i][j-1],
                               price[j] + prevDiff);
        }
    }
    return profit[k][n-1];
}
https://www.reddit.com/r/leetcode/comments/73dd24/188_best_time_to_buy_and_sell_stock_iv/
The idea is that we are doing repeated work by looping through the array, at every given junction of the table. Thus, for any given row, we can keep track of a variable "prevDiff". If we are currently at day i, and trying to calculate the maximum profit able to be made at day i, then we need to figure out the best possible day to have bought a stock after making a profit.
Thus prevDiff = max(prevDiff, dp[j][k-1] - nums[j])
Then, today would just be dp[i][j] = max(prevDiff + nums[i], dp[i-1][k]) because we already paid the price to buy the "prevdiff" which is why we subtracted nums[j]. We try to complete the transaction today by adding nums[i]
可以对上面的代码优化，注意到枚举j是为了寻找第i天之前交易x-1次的利润最大，而这个过程重复计算了很多，可以进行优化，只需要保存i之前最大的dp[j][x – 1] – prices[j]即可。这样复杂度就变为O(nk)

    int maxProfit(int k, vector<int>& prices) {
        if(prices.empty()) return 0;
        int ans = 0;
        if(k >= prices.size() / 2){
            for(int i = 1; i < prices.size(); ++i){
                if(prices[i] > prices[i - 1])
                    ans += prices[i] - prices[i - 1];
            }
            return ans;
        }
        vector<vector<int>> dp(prices.size(), vector<int>(k + 1, 0));
        for(int x = 1; x <= k; ++x){
            int max_pre = -prices[0]; //+ dp[0][x - 1];
            for(int i = 1; i < prices.size(); ++i){
                dp[i][x] = max(dp[i - 1][x], max_pre + prices[i]);
                max_pre = max(max_pre, dp[i][x - 1] - prices[i]);
            }
            ans = max(ans, dp[prices.size() - 1][x]);
        }
        return ans;
    }

X. http://bookshadow.com/weblog/2015/02/18/leetcode-best-time-to-buy-and-sell-stock-iv/
问题的实质是从长度为n的prices数组中挑选出至多2 * k个元素，组成一个交易（买卖）序列。

交易序列中的首次交易为买入，其后卖出和买入操作交替进行。

总收益为交易序列中的偶数项之和 - 奇数项之和。
dp[j]表示完成j次交易时的最大收益，转移方程如下：
dp[j] = max(dp[j], dp[j - 1] + prices[i] * [1, -1][j % 2])
当j为奇数时，交易类型为买入；

当j为偶数时，交易类型为卖出。
由于直接采用动态规划会返回Time Limit Exceeded，可以针对题目部分样例做出下面的优化：
令最大交易次数为k，数组长度为size；

则当k > size / 2时，问题可以转化为：Best Time to Buy and Sell Stock II
第二种方法随不影响结果的正确性，但是逻辑上是错误的，因为它实际上的意义是允许了同一天有又买又卖

public int maxProfit(int k, int[] prices) { if (prices.length == 0) return 0; // if k is big compared to prices.length, don't bother with dp if (k > prices.length / 2) return maxProfitInfinite(prices); int[] dp = new int[1 + k * 2]; for (int i = 0; i < k; ++i) dp[i * 2 + 1] = - prices[0]; for (int p : prices) { for (int i = k; i > 0; --i) { dp[2 * i] = Math.max(dp[2 * i], dp[2 * i - 1] + p); dp[2 * i - 1] = Math.max(dp[2 * i - 1], dp[2 * i - 2] - p); } } return dp[k * 2]; }

X.
https://www.bbsmax.com/A/RnJW2BXrzq/
能不能用一个二维数组profit[t,i]表示  通过T次交易 在第I个商品能获得的最大利润   那么profit[k,n]就是在第N个商品通过K次交易能获得的最大利润
根据推理 得出下列方程
profit[t,i]=max(profit(t,i-1),prices[i]+tmp)
tmp=max(tmp,profit(t-1,i-1)-prices[i])
tmp初始化为第一个商品的价格
这里解释一下 tmp的方程怎么来的 profit(t-1,i-1)-prices[i]表明 在第i-1个商品通过t-1次交易获得利润后 再买入第i个商品 并且跟之前的tmp比较取最大值
profit[t,i]中prices[i]+tmp 表明在之前的tmp基础上 卖出第I个商品获得的利润  和除去第I个商品获得的利润作比较 最大值
https://leetcode.com/discuss/25603/a-concise-dp-solution-in-java
The general idea is DP, while I had to add a "quickSolve" function to tackle some corner cases to avoid TLE.
DP: t(i,j) is the max profit for up to i transactions by time j (0<=i<=K, 0<=j<=T).
Actually, tmpMax = Math.max(tmpMax, t[i - 1][j] - prices[j]); - this is kind of misleading should be tmpMax = Math.max(tmpMax, t[i - 1][j-1] - prices[j]); - by changing to this, it is still acceptable, and easy to understand.
tmpMax means the maximum profit of just doing at most i-1 transactions, using at most first j-1 prices, and buying the stock at price[j] - this is used for the next loop.

Because buy and sell prices may not be the same, when k>len/2, that means we can do as many transactions as we want. So, in case k>len/2, this problem is same to Best Time to Buy and Sell Stock III.
t[i][j] = Math.max(t[i][j - 1], prices[j] + tmpMax) gives us the maximum price when we sell at this price;
tmpMax = Math.max(tmpMax, t[i - 1][j] - prices[j]) gives us the value when we buy at this price and leave this value for prices[j+1].
    public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        if (k >= len / 2) return quickSolve(prices);
        
        int[][] t = new int[k + 1][len];
        for (int i = 1; i <= k; i++) {
            int tmpMax =  -prices[0];
            for (int j = 1; j < len; j++) {
                t[i][j] = Math.max(t[i][j - 1], prices[j] + tmpMax);
                tmpMax =  Math.max(tmpMax, t[i - 1][j - 1] - prices[j]);
            }
        }
        return t[k][len - 1];
    }
    

    private int quickSolve(int[] prices) {
        int len = prices.length, profit = 0;
        for (int i = 1; i < len; i++)
            // as long as there is a price gap, we gain a profit.
            if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
        return profit;
    }
X. Local + Global DP
http://www.cnblogs.com/grandyang/p/4295761.html
http://zhuixin8.com/2016/10/02/leetcode-188/
http://www.jiuzhang.com/solutions/best-time-to-buy-and-sell-stock-iv/
我们定义local[i][j]为在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润，此为局部最优。然后我们定义global[i][j]为在到达第i天时最多可进行j次交易的最大利润，此为全局最优。它们的递推式为：

local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff)
global[i][j] = max(local[i][j], global[i - 1][j])，
但这道题还有个坑，就是如果k的值远大于prices的天数，比如k是好几百万，而prices的天数就为若干天的话，上面的DP解法就非常的没有效率，应该直接用Best Time to Buy and Sell Stock II 买股票的最佳时间之二的方法来求解，所以实际上这道题是之前的二和三的综合.
    int maxProfit(int k, vector<int> &prices) {
        if (prices.empty()) return 0;
        if (k >= prices.size()) return solveMaxProfit(prices);
        int g[k + 1] = {0};
        int l[k + 1] = {0};
        for (int i = 0; i < prices.size() - 1; ++i) {
            int diff = prices[i + 1] - prices[i];
            for (int j = k; j >= 1; --j) {
                l[j] = max(g[j - 1] + max(diff, 0), l[j] + diff);
                g[j] = max(g[j], l[j]);
            }
        }
        return g[k];
    }
    int solveMaxProfit(vector<int> &prices) {
        int res = 0;
        for (int i = 1; i < prices.size(); ++i) {
            if (prices[i] - prices[i - 1] > 0) {
                res += prices[i] - prices[i - 1];
            }
        }
        return res;
    }
http://buttercola.blogspot.com/2015/08/leetcode-best-time-to-buy-and-sell.html
Also check http://hehejun.blogspot.com/2015/01/algorithm-best-time-to-buy-and-sell.html
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].
    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. 
    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];
    }
http://blog.csdn.net/linhuanmars/article/details/23236995
第一个是全局到i-1天进行j-1次交易，然后加上今天的交易，如果今天是赚钱的话（也就是前面只要j-1次交易，最后一次交易取当前天），第二个量则是取local第i-1天j次交易，然后加上今天的差值（这里因为local[i-1][j]比如包含第i-1天卖出的交易，所以现在变成第i天卖出，并不会增加交易次数，而且这里无论diff是不是大于0都一定要加上，因为否则就不满足local[i][j]必须在最后一天卖出的条件了）
这里的模型是比较复杂的，主要是在递推式中，local和global是交替求解的。
https://www.jianshu.com/p/26f792f83ee4
典型的动态规划，并且利用局部和全局最优，这种思想值得仔细体会，好好掌握。
这种局部最优与全局最优问题
global[i][j] = max(local[i][j], global[i - 1][j])
很容易知道上面这个递推式。
关键在于求取局部最优的递推式，在本题中
local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff)
这里我们需要两个递推公式来分别更新两个变量local和global
我们定义local[i][j]为在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润，此为局部最优。然后我们定义global[i][j]为在到达第i天时最多可进行j次交易的最大利润，此为全局最优
局部最优解的递推式可以这样理解：
  • 在i-1天时，正在进行第j次交易，所以我们最后一天必须将股票卖出，而且这是算在第j次交易当中的，这种情况下，local[i - 1][j] + diff，只需将i-1天的局部最优解加上最后一天卖出的差值即可，相当于将最后一次交易多延迟了一天
  • 第二种情况，就是在第i-1天进行j-1次交易的全局最优解，我们在最后一天还得进行一次交易，必须卖出，如果diff大于0，那么就在第i-1天买进，i天卖出，如果小于0，就直接在第i天买进又卖出，只是为了满足j次交易，就相当于没有交易，即加上0就可以了。
    这道题还有一个陷阱，可以优化的地方，就是如果k>=prices.length/2。那我们可以理解可以进行任意次交易了，因为有效交易都需要两天来完成，所以直接使用贪心法就可以算出来了。
https://leetcode.com/discuss/62026/clean-java-dp-solution-with-comment
/** * dp[i, j] represents the max profit up until prices[j] using at most i transactions. * dp[i, j] = max(dp[i, j-1], prices[j] - prices[jj] + dp[i-1, jj]) { jj in range of [0, j-1] } * = max(dp[i, j-1], prices[j] + max(dp[i-1, jj] - prices[jj])) * dp[0, j] = 0; 0 transactions makes 0 profit * dp[i, 0] = 0; if there is only one price data point you can't make any transaction. */ public int maxProfit(int k, int[] prices) { int n = prices.length; if (n <= 1) return 0; //if k >= n/2, then you can make maximum number of transactions. if (k >= n/2) { int maxPro = 0; for (int i = 1; i < n; i++) { if (prices[i] > prices[i-1]) maxPro += prices[i] - prices[i-1]; } return maxPro; } int[][] dp = new int[k+1][n]; for (int i = 1; i <= k; i++) { int localMax = dp[i-1][0] - prices[0]; for (int j = 1; j < n; j++) { dp[i][j] = Math.max(dp[i][j-1], prices[j] + localMax); localMax = Math.max(localMax, dp[i-1][j] - prices[j]); } } return dp[k][n-1]; }
https://gist.github.com/ElninoFong/d08051d98e634991cd93
这道题是Best Time to Buy and Sell Stock的扩展，现在我们最多可以进行两次交易。
我们仍然使用动态规划来完成，事实上可以解决非常通用的情况，也就是最多进行k次交易的情况。
这里我们先解释最多可以进行k次交易的算法，然后最多进行两次我们只需要把k取成2即可。
我们还是使用“局部最优和全局最优解法”。
我们维护两种量，一个是当前到达第i天可以最多进行j次交易，最好的利润是多少（global[i][j]），
另一个是当前到达第i天，最多可进行j次交易，并且最后一次交易在当天卖出的最好的利润是多少（local[i][j]）。
下面我们来看递推式，全局的比较简单，
global[i][j]=max(local[i][j],global[i-1][j])，
也就是去当前局部最好的，和过往全局最好的中大的那个（因为最后一次交易如果包含当前天一定在局部最好的里面，
否则一定在过往全局最优的里面）。
全局（到达第i天进行j次交易的最大收益） = max{局部（在第i天交易后，恰好满足j次交易），全局（到达第j-1天时已经满足j次交易）}
对于局部变量的维护，递推式是
local[i][j]=max(global[i-1][j-1]+max(diff,0),local[i-1][j]+diff)，
也就是看两个量，第一个是全局到i-1天进行j-1次交易，然后加上今天的交易，
如果今天是赚钱的话（也就是前面只要j-1次交易，最后一次交易取当前天），
第二个量则是取local第i-1天j次交易，然后加上今天的差值
（这里因为local[i-1][j]比如包含第i-1天卖出的交易，所以现在变成第i天卖出，
并不会增加交易次数，而且这里无论diff是不是大于0都一定要加上，
因为否则就不满足local[i][j]必须在最后一天卖出的条件了）。
局部（在第i天交易后，总共交易了j次） =  max{情况2，情况1}
情况1：在第i-1天时，恰好已经交易了j次（local[i-1][j]），那么如果i-1天到i天再交易一次：
即在第i-1天买入，第i天卖出（diff），则这不并不会增加交易次数！
【例如我在第一天买入，第二天卖出；然后第二天又买入，第三天再卖出的行为  和   第一天买入，
第三天卖出  的效果是一样的，其实只进行了一次交易！因为有连续性】
情况2：第i-1天后，共交易了j-1次（global[i-1][j-1]），因此为了满足“第i天过后共进行了j次交易，
且第i天必须进行交易”的条件：我们可以选择1：在第i-1天买入，然后再第i天卖出（diff），
或者选择在第i天买入，然后同样在第i天卖出（收益为0）。
上面的算法中对于天数需要一次扫描，而每次要对交易次数进行递推式求解，所以时间复杂度是O(n*k)，
如果是最多进行两次交易，那么复杂度还是O(n)。空间上只需要维护当天数据皆可以，所以是O(k)，当k=2，则是O(1)。

X. 
https://blog.csdn.net/qq508618087/article/details/51678245
当k < len/2时，可以记录k次交易每次买之后和卖以后最大的利润：

１．第ｉ次买操作买下当前股票之后剩下的最大利润为第(i-1)次卖掉股票之后的利润－当前的股票价格．状态转移方程为：

　　　　buy[i] = max(sell[i-1]- curPrice, buy[i]);

２．第ｉ次卖操作卖掉当前股票之后剩下的最大利润为第ｉ次买操作之后剩下的利润＋当前股票价格．状态转移方程为：

　　　　sell[i] = max(buy[i]+curPrice, sell[i]);
    int maxProfit(int k, vector<int>& prices) {
        if(prices.size() ==0) return 0;
        int len = prices.size(), ans =0　;
        if(k >= len/2)
        {
            for(int i = 1; i < len; i++)
                if(prices[i]-prices[i-1])>0) ans += prices[i]-prices[i-1];
            return ans;
        }
        vector<int> buy(len+1, INT_MIN), sell(len+1, 0);
        for(auto val: prices)
        {
            for(int i =1; i <= k; i++)
            {
                buy[i] = max(sell[i-1]-val, buy[i]);
                sell[i] = max(buy[i]+val, sell[i]);
            }
        }
        return sell[k];
    }

X.  DP
https://discuss.leetcode.com/topic/24079/easy-understanding-and-can-be-easily-modified-to-different-situations-java-solution/
https://leetcode.com/discuss/57669/understanding-easily-modified-different-situations-solution
You can just simply return unhold[prices.length-1][k] instead of Math.max(hold[prices.length-1][k],unhold[prices.length-1][k]).
unhold[prices.length-1][k] must be greater than or equal to hold[prices.length-1][k]
The basic idea is to create two tables. hold and unhold.
hold[i][j] means the maximum profit with at most j transaction for 0 to i-th day. hold means you have a stock in your hand.
unhold[i][j] means the maximum profit with at most j transaction for 0 to i-th day. unhold means you don't have a stock in your hand.
The equation is
hold[i][j] = Math.max(unhold[i-1][j]-prices[i],hold[i-1][j]);
unhold[i][j] = Math.max(hold[i-1][j-1]+prices[i],unhold[i-1][j]);
when you sell your stock this is a transaction but when you buy a stock, it is not considered as a full transaction. so this is why the two equation look a little different.
And we have to initiate hold table when k = 0.
When the situation is you can not buy a new stock at the same day when you sell it. For example you can only buy a new stock after one day you sell it. The same idea. Another situation is when you have to pay a transaction fee for each transaction, just make a modification when you sell it, So just change the unhold equation a little.
    //hold[i][k]  ith day k transaction have stock and maximum profit
    //unhold[i][k] ith day k transaction do not have stock at hand and maximum profit
    public int maxProfit(int k, int[] prices) {
        if(k>prices.length/2) return maxP(prices);
        int[][] hold = new int[prices.length][k+1];
        int[][] unhold = new int[prices.length][k+1];
        hold[0][0] = -prices[0];
        for(int i=1;i<prices.length;i++) hold[i][0] = Math.max(hold[i-1][0],-prices[i]);
        for(int j=1;j<=k;j++) hold[0][j] = -prices[0];
        for(int i=1;i<prices.length;i++){
            for(int j=1;j<=k;j++){
                hold[i][j] = Math.max(unhold[i-1][j]-prices[i],hold[i-1][j]);
                unhold[i][j] = Math.max(hold[i-1][j-1]+prices[i],unhold[i-1][j]);
            }
        }
        return Math.max(hold[prices.length-1][k],unhold[prices.length-1][k]);
    }
    public int maxP(int[] prices){
        int res =0;
        for(int i=0;i<prices.length;i++){
            if(i>0 && prices[i] > prices[i-1]){
                res += prices[i]-prices[i-1];
            }
        }
        return res;
    }
Based on your idea, this is the shorter version in Java:
public int maxProfit(int k, int[] prices) {
    if(k == 0 || prices.length < 2)
        return 0;
    if(k > prices.length / 2)
        return noLimit(prices);
    
    // hold[i][j]: For at most i transactions, the max profit on jth day with a stock in hand.
    // unhold[i][j]: For at most i transactions, the max profit on jth day without a stock in hand
    int[][] hold = new int[k+1][prices.length];
    int[][] unhold = new int[k+1][prices.length];
    for(int i = 1; i <= k; i++) {
        hold[i][0] = -prices[0];
        unhold[i][0] = 0;
        for(int j = 1; j < prices.length; j++) {
            hold[i][j] = Math.max(-prices[j] + unhold[i-1][j], hold[i][j-1]); // Buy or not buy
            unhold[i][j] = Math.max(prices[j] + hold[i][j-1], unhold[i][j-1]); // Sell or not sell
        }
    }
    return unhold[k][prices.length-1];
}
private int noLimit(int[] prices) { // Solution from Best Time to Buy and Sell Stock II
    int max = 0;
    for(int i = 0; i < prices.length-1; i++) {
        if(prices[i+1] > prices[i])
            max += prices[i+1] - prices[i];
    }
    return max;
}
My solution is similar, but only takes o(k) extra space.
    public int maxProfit(int k, int[] prices) {
        if (prices == null || prices.length <= 1 || k == 0) { return 0;}
        if (k >= prices.length / 2) {return unlimited(prices);}
        int[] soldN = new int[k + 1], buyN = new int[k + 1];
        for (int i = 0; i <= k; i++) {
            buyN[i] = Integer.MIN_VALUE;
        }
        for (int i = 0; i < prices.length; i++) {
            for (int j = 1; j <= k; j++) {
                buyN[j] = Math.max(buyN[j], soldN[j - 1] - prices[i]);
                soldN[j] = Math.max(soldN[j], buyN[j] + prices[i]);
            }
        }
        return soldN[k];
    }
    
    private int unlimited(int[] prices) {
        int sum = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            sum += prices[i + 1] - prices[i] > 0 ? prices[i + 1] - prices[i] : 0;
        }
        return sum;
    }
https://leetcode.com/discuss/88005/2-ms-java-dp-solution-beats-99-87%25
public int maxProfit(int k, int[] prices) { if (k <= 0 || prices == null || prices.length <= 0) return 0; if (k > prices.length / 2) { // in this case, it's the same problem as Best Time to Buy & Sell Stock II int max = 0; for (int i = 0; i < prices.length - 1; i++) { int diff = prices[i + 1] - prices[i]; max += diff>0 ? diff : 0; } return max; } else { int [] buy = new int[k]; int [] sell = new int[k]; Arrays.fill(buy, Integer.MIN_VALUE); for (int price: prices) { int tmp = 0; for (int i = 0; i < k; i ++) { int buffer = 0; // used to avoid duplicate calculation buffer = tmp - price; if (buy[i] < buffer) buy[i] = buffer; buffer = buy[i] + price; if (sell[i] < buffer) sell[i] = buffer; tmp = sell[i]; } } return sell[k - 1]; } }


http://liangjiabin.com/blog/2015/04/leetcode-best-time-to-buy-and-sell-stock.html
特殊动态规划法。传统的动态规划我们会这样想，到第i天时进行j次交易的最大收益，要么等于到第i-1天时进行j次交易的最大收益（第i天价格低于第i-1天的价格），要么等于到第i-1天时进行j-1次交易，然后第i天进行一次交易（第i天价格高于第i-1天价格时）。于是得到动规方程如下（其中diff = prices[i] – prices[i – 1]）：
profit[i][j] = max(profit[i – 1][j], profit[i – 1][j – 1] + diff)
看起来很有道理，但其实不对，为什么不对呢？因为diff是第i天和第i-1天的差额收益，如果第i-1天当天本身也有交易呢，那么这两次交易就可以合为一次交易，这样profit[i – 1][j – 1] + diff实际上只进行了j-1次交易，而不是最多可以的j次，这样得到的最大收益就小了。
那么怎样计算第i天进行交易的情况的最大收益，才会避免少计算一次交易呢？我们用一个局部最优解和全局最有解表示到第i天进行j次的收益，这就是该动态规划的特殊之处。
其中的local[i – 1][j] + diff就是为了避免第i天交易和第i-1天交易合并成一次交易而少一次交易收益。
其中局部最优值是比较前一天并少交易一次的全局最优加上大于0的差值，和前一天的局部最优加上差值后相比，两者之中取较大值，而全局最优比较局部最优和前一天的全局最优。

但这道题还有个坑，就是如果k的值远大于prices的天数，比如k是好几百万，而prices的天数就为若干天的话，上面的DP解法就非常的没有效率，应该直接用Best Time to Buy and Sell Stock II 买股票的最佳时间之二的方法来求解，所以实际上这道题是之前的二和三的综合体。
    int maxProfit(int k, vector<int> &prices) {
        if (prices.empty()) return 0;
        if (k >= prices.size()/2) return solveMaxProfit(prices);
        int g[k + 1] = {0};
        int l[k + 1] = {0};
        for (int i = 0; i < prices.size() - 1; ++i) {
            int diff = prices[i + 1] - prices[i];
            for (int j = k; j >= 1; --j) {
                l[j] = max(g[j - 1] + max(diff, 0), l[j] + diff);
                g[j] = max(g[j], l[j]);
            }
        }
        return g[k];
    }
    int solveMaxProfit(vector<int> &prices) {
        int res = 0;
        for (int i = 1; i < prices.size(); ++i) {
            if (prices[i] - prices[i - 1] > 0) {
                res += prices[i] - prices[i - 1];
            }
        }
        return res;
    }
Different Solution: Better Space.
http://bookshadow.com/weblog/2015/02/18/leetcode-best-time-to-buy-and-sell-stock-iv/
动态规划（Dynamic Programming）
问题的实质是从长度为n的prices数组中挑选出至多2 * k个元素，组成一个交易（买卖）序列。
交易序列中的首次交易为买入，其后卖出和买入操作交替进行。

总收益为交易序列中的偶数项之和 - 奇数项之和。
dp[j]表示完成j次交易时的最大收益，转移方程如下：

dp[j] = max(dp[j], dp[j - 1] + prices[i] * [1, -1][j % 2])
当j为奇数时，交易类型为买入；
当j为偶数时，交易类型为卖出。
def maxProfit(self, k, prices): size = len(prices) if k > size / 2: return self.quickSolve(size, prices) dp = [None] * (2 * k + 1) dp[0] = 0 for i in range(size): for j in range(min(2 * k, i + 1) , 0 , -1): dp[j] = max(dp[j], dp[j - 1] + prices[i] * [1, -1][j % 2]) return max(dp) def quickSolve(self, size, prices): sum = 0 for x in range(size - 1): if prices[x + 1] > prices[x]: sum += prices[x + 1] - prices[x] return sum
http://www.zhuangjingyang.com/leetcode-best-time-to-buy-and-sell-stock-series/
Same as previous solution:
t[i][j] = Math.max(t[i][j – 1], prices[j] + buy) 即得出在prices[j]卖出时的最大利润; 
buy= Math.max(buy, t[i – 1][j – 1] – prices[j]) 则得出在prices[j]买进后剩下的钱，留待下次卖出.

Recursive Version: Inefficient
https://angshukutu.wordpress.com/2015/01/11/given-a-vector-of-integers-vi-represent-the-stock-price-on-day-i-now-you-may-do-at-most-k-transactions-you-must-sell-your-stock-before-you-buy-it-again-and-that-means-you-can-not-have-two-stocks/
public static int getMaxProfit(int[] v, int k, int s, int e){
    if(s == e || k == 0){
        return 0;
    }
    int start = v[s];
    for(int i = s+1; i<=e; i++ ){
        int end = v[i];
        int profit = end - start;
        for(int j = k-1; j>=0; j--){
            int maxRest = getMaxProfit(v, j, i, e);
            int maxProfit = Math.Max(profit, maxprofit);
            if(maxProfit > max)
                max = maxProfit;
        }
    }
    return max;
}

http://maskray.me/blog/2015-03-27-leetcode-best-time-to-buy-and-sell-stock-iv
leetcode-Best Time to Buy and Sell Stock 系列
To read: http://leetcode.tgic.me/best-time-to-buy-and-sell-stock-iv/index.html
Read full article from The Code Sniper: 188. Best Time to Buy and Sell Stock IV Leetcode Java
at
Labels: , , , , , , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts

  • Archives
  • HackerRank: Pacman A*
    HackerRank: Pacman A* In the previous game, you performed UCS on the PacMan grid. In this game we use AStar algorithm to reduce the nodes...
  • LeetCode 471 - Encode String with Shortest Length
    Related:  LeetCode 394 - Decode String http://bookshadow.com/weblog/2016/12/11/leetcode-encode-string-with-shortest-length/ Given a  non...
  • HackerRank: PacMan - BFS
    HackerRank: PacMan - BFS In the previous game, you performed DFS on the PacMan grid. It was seen that DFS might not always give the short...
  • DropBox Interview Misc
    https://paper.dropbox.com/doc/Interview-Notes-Dropbox-wl7npLjRBjrAKA5AOBsaM Behavioural https://www.paysa.com/blog/2017/04/05/what-to...
  • Buttercola: Buddy System
    Buttercola: Buddy System Given a complete binary tree with nodes of values of either 1 or 0, the following rules always hold: 1. A node...
  • LeetCode 988 - Smallest String Starting From Leaf
    https://leetcode.com/problems/smallest-string-starting-from-leaf/ Given the  root  of a binary tree, each node has a value from  0  to  2...
  • LeetCode 752 - Open the Lock
    https://leetcode.com/problems/open-the-lock/description/ You have a lock in front of you with 4 circular wheels. Each wheel has 10 slot...
  • Simple Text Editor - HackerRank
    https://www.hackerrank.com/challenges/simple-text-editor In this problem, your task is to implement a simple text editor. Initially, a fi...
  • LFU Cache
    http://www.jiuzhang.com/solutions/lfu-cache/ https://github.com/chirino/hawtdb/blob/master/hawtdb/src/main/java/org/fusesource/hawtdb/util...