[LeetCode][Java] Best Time to Buy and Sell Stock IV

题目：

Say you have an array for which theithelement is the price of a given stock on dayi.

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

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

题意：

给定一个数组，数组中第 i 个元素，表示给定的一只股票在第 i 天的价格.

设计一个算法找出最大的收益。你最多被允许k 次交易。

注意：

同一时间你不能进行多次交易。（即：在你必须先卖掉这只股票才能再次购买）

算法分析：

采用动态规划进行求解，使用局部最优和全局最优解法

由于要考虑交易次数，维护量应该就是一个二维数组。

定义维护量：

global[i][j]:在到达第i天时最多可进行j次交易的最大利润，此为全局最优

local[i][j]:在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润，此为局部最优

定义递推式：

global[i][j]=max(global[i-1][j],local[i][j]);即第i天没有交易，和第i天有交易

local[i][j]=max(global[i-1][j-1]+max(diff,0),local[i-1][j]+diff) diff=price[i]-price[i-1];

就是看两个量，第一个是全局到i-1天进行j-1次交易，然后加上今天的交易，如果今天是赚钱的话（也就是前面只要j-1次交易，最后一次交易取当前天），第

二个量则是取local第i-1天j次交易，然后加上今天的差值（这里因为local[i-1][j]比如包含第i-1天卖出的交易，所以现在变成第i天卖出，并不会增加交易次数，，

而且这里无论diff是不是大于0都一定要加上，因为否则就不满足local[i][j]必须在最后一天卖出的条件了）

这道题还有个坑，就是如果k的值远大于prices的天数，比如k是好几百万，而prices的天数就为若干天的话，上面的DP解法就非常的没有效率，应该直接用

《Best Time to Buy and Sell Stock II》的方法来求解，所以实际上这道题是之前的二和三的综合体。

AC代码：

<span style="font-family:Microsoft YaHei;font-size:12px;">public class Solution {public int maxProfit(int k, int[] prices){if(prices==null || prices.length==0)return 0;if(k>prices.length)//k次数大于天数时，转化为问题《Best Time to Buy and Sell Stock II》–无限次交易的情景{if(prices==null)return 0;int res=0;for(int i=0;i<prices.length-1;i++){int degit=prices[i+1]-prices[i];if(degit>0)res+=degit;}return res;}/*定义维护量：global[i][j]:在到达第i天时最多可进行j次交易的最大利润，此为全局最优local[i][j]:在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润，此为局部最优定义递推式：global[i][j]=max(global[i-1][j],local[i][j]);即第i天没有交易，和第i天有交易local[i][j]=max(global[i-1][j-1]+max(diff,0),local[i-1][j]+diff) diff=price[i]-price[i-1];*/int[][] global=new int[prices.length][k+1];int[][] local=new int[prices.length][k+1];for(int i=0;i<prices.length-1;i++){int diff=prices[i+1]-prices[i];for(int j=0;j<=k-1;j++){local[i+1][j+1]=Math.max(global[i][j]+Math.max(diff,0),local[i][j+1]+diff);global[i+1][j+1]=Math.max(global[i][j+1],local[i+1][j+1]);}}return global[prices.length-1][k];}}</span>

版权声明：本文为博主原创文章，转载注明出处

没有什么可留恋，只有抑制不住的梦想，没有什么可凭仗，