[LeetCode] 188. Best Time to Buy and Sell Stock IV LeetCode

题：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
题目 【[LeetCode] 188. Best Time to Buy and Sell Stock IV】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).
Example 1:

Input: [2,4,1], k = 2 Output: 2 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: [3,2,6,5,0,3], k = 2 Output: 7 Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

题目大意求最多买 k次的情况下，最大的股票收益。
思路动态规划与问题转化。
2个状态：
int[][] local：local[i][j]表示到第i天时至少完成j次交易并且最后一次交易发生在第i天时的最大收益。
int[][] global：global[i][j]表示到第i天时至少完成j次交易的最大收益，最后一次交易不一定发生在第i天。
状态转移方程：
diff = nums[i] - nums[i-1]
local[i][j] = max(global[i-2][j-1] + diff if i>=2 else 0, global[i-1][j-1],local[i-1][j] + diff)
即，第i天刚发生第j次交易的最大收益是

第i-2天已经发生第j-1次交易的最大收益 + 第i-1天买且第i天卖的收益。
第i-1天已经发生至少第j-1次交易的最大收益（相当于第j次交易什什么都不做）
第i-1天刚j次交易，然后加上今天的差值（这里因为local[i-1][j]比如包含第i-1天卖出的交易，所以现在变成第i天卖出，并不会增加交易次数，而且这里无论diff是不是大于0都一定要加上，因为否则就不满足local[i][j]必须在最后一天卖出的条件了）

取以上 3 种的最大值。
其中 1,2 可以合并为
global[i-1][j-1]+max(diff,0)
故：
local[i][j] = max(global[i-1][j-1]+max(diff,0), local[i-1][j]+diff)
global[i][j] = max(global[i-1][j],local[i][j])
即，在第i天已经发生j次交易的最大收益是在第i-1天已经发生j次交易的最大收益和在第i天刚发生第j次交易的最大收益中较大值。
初始化状态：均为 0；
参考：https://blog.csdn.net/smile_watermelon/article/details/47445981
当 k >>2 >= nums.length 时候，可以看做任务为任意次交易。因为每次交易至少需要 2天。最大允许的交易次数等于在nums.length天最多能完成的交易次数，所以可看作可以无限交易。
这样效率更高，因为 k 可能很大，为了迭代k次，会占用大量内存与计算力导致不过了。
local[i][j] 未合并

class Solution { public int maxProfit(int k, int[] prices) { if(k<<1>=prices.length){ return infiniteMaxProfit(prices); } 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] = i<2?0:global[i-2][j-1]; local[i][j] = Math.max(local[i][j] + diff,global[i-1][j-1]); local[i][j] = Math.max(local[i][j],local[i-1][j] + diff); global[i][j] = Math.max(local[i][j],global[i-1][j]); } } return global[prices.length-1][k]; }private int infiniteMaxProfit(int[] prices) { int []buy = new int[prices.length+1]; int []sell = new int[prices.length+1]; buy[0] = Integer.MIN_VALUE; for(int i = 1; i <= prices.length ; i++){ buy[i] = Math.max(buy[i-1],sell[i-1]-prices[i-1]); sell[i] = Math.max(sell[i-1],buy[i-1]+prices[i-1]); } return sell[prices.length]; } }

local[i][j] 合并

class Solution { public int maxProfit(int k, int[] prices) { if(k<<1>=prices.length){ return infiniteMaxProfit(prices); } 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(diff,0),local[i-1][j] + diff); global[i][j] = Math.max(local[i][j],global[i-1][j]); } } return global[prices.length-1][k]; }private int infiniteMaxProfit(int[] prices) { int []buy = new int[prices.length+1]; int []sell = new int[prices.length+1]; buy[0] = Integer.MIN_VALUE; for(int i = 1; i <= prices.length ; i++){ buy[i] = Math.max(buy[i-1],sell[i-1]-prices[i-1]); sell[i] = Math.max(sell[i-1],buy[i-1]+prices[i-1]); } return sell[prices.length]; } }

由于local[i][j] 、 global[i][j] 只是涉及 [i-1][j] 与 [i-1][j-1] ，所以可以优化，但注意到 j-1 ，对 j 迭代需要从后往前。

class Solution { public int maxProfit(int k, int[] prices) { if(k<<1>=prices.length){ return infiniteMaxProfit(prices); }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 >= 1 ; j--){ local[j] = Math.max(global[j-1] + Math.max(diff,0),local[j] + diff); global[j] = Math.max(local[j],global[j]); } } return global[k]; }private int infiniteMaxProfit(int[] prices) { int []buy = new int[prices.length+1]; int []sell = new int[prices.length+1]; buy[0] = Integer.MIN_VALUE; for(int i = 1; i <= prices.length ; i++){ buy[i] = Math.max(buy[i-1],sell[i-1]-prices[i-1]); sell[i] = Math.max(sell[i-1],buy[i-1]+prices[i-1]); } return sell[prices.length]; } }