问题描述
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.
问题分析： 该问题就是在股票买卖问题的基础之上加上最大交易次数k的限制条件，实际上变成了0-1背包问题。选择2*k个数，使得效益最大，但是对于不同的数存在不同的计算方式。 解题思路：
问题的实质是从长度为n的prices数组中挑选出至多2*k个元素，组成一个交易序列。 交易序列中的首次交易为买入，其后卖出和买入操作交替进行。 总收益为交易序列中的偶数项之和 - 奇数项之和。dp[j]表示完成j次交易时最大收益，转移方程： dp[j]=max(dp[j],dp[j-1]+(j%2==0?1:-1)*prices[i])
当j为奇数时，交易类型为买入；当j为偶数时，交易类型为卖出。注意：当n<2*k时，直接计算最大收益即可。 代码如下：
public int maxProfit(int k, int[] prices) { int n=prices.length; if(n<=k*2) return getProfit(prices); int[]dp=new int[2*k+1]; for(int i=1;i<=2*k;i++) dp[i]=Integer.MIN_VALUE; for(int i=0;i<n;i++){ for(int j=1;j<=2*k;j++){ dp[j]=Math.max(dp[j],dp[j-1]+(j%2==0?1:-1)*prices[i]); } } return dp[2*k]; } public int getProfit(int[] prices){ int sum=0; for(int i=0;i<prices.length-1;i++){ if(prices[i+1]-prices[i]>0) sum+=prices[i+1]-prices[i]; } return sum; }其实如果利用之前没有限制交易次数问题的解法同样有：（注意，sell[j]=max(sell[j],buy[j]+prices[i])
public int maxProfit(int k, int[] prices) { if (k < 1 || prices == null || prices.length < 2) return 0; if (k >= prices.length/2) { int max = 0; for(int i=1; i<prices.length; i++) max += Math.max(0, prices[i]-prices[i-1]); return max; } int[] buy = new int[k]; int[] sell = new int[k]; Arrays.fill(buy, Integer.MIN_VALUE); for(int i=0; i<prices.length; i++) { for(int j=0; j<k; j++) { buy[j] = Math.max(buy[j], j==0?-prices[i]:sell[j-1]-prices[i]); sell[j] = Math.max(sell[j], buy[j]+prices[i]); } } return sell[k-1]; }参考链接： http://bookshadow.com/weblog/2015/02/18/leetcode-best-time-to-buy-and-sell-stock-iv/ http://lib.csdn.net/article/datastructure/21116
