Best Time to Buy and Sell Stock IV

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).

刚拿到这道题目的时候完全没有思路，想借鉴 Best Time to Buy and Sell Stock III 的思路，但是复杂度太高，过不了大的test。看了许多大牛的文章，大家的思路基本上都来源于这篇博客，http://blog.csdn.net/linhuanmars/article/details/23236995。 文章的思路很好，用local和global两个数组，基于DP来解决这个问题，但是我一直看不懂关于local的递推关系式，

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

我觉得这个关系大致正确，但仔细推敲却不make sense。

local[i-1][j]+diff这一部分可以理解，local[i-1][j]就是进行了j次transaction，其中最后一次是在(i-1)的位置卖出。local[i-1][j]+diff就是把最后一次卖出的位置从i-1移到了i，因为相当于合并了两次交易，所以总共的交易次数还是j。

global[i-1][j-1]+max(diff,0)的含义就很confusing了，global[i-1][j-1]意思是到(i-1)为止，在交易了最多(j-1)次的情况下的最大收益，要从这个得到local[i][j]，就要保证在i的位置卖一次，但是global[i-1][j-1]有可能会包含在(i-1)的位置卖股票的情况，这种情况下，在i的位置再卖一次显然没有任何意义。

基于这些大牛的思路，我自己总结的更加容易理解的关系是这样的。

在计算local[i][j]的时候，这里的关键因素是多了一个元素，prices[i]。local[i][j]的意思是交易了j次，并且最后一次的卖发生在i。这个元素究竟会怎样影响最大收益呢？它有两种方式影响最大收益。

1. 把(i-1)处的卖移到i处，由于这相当于合并了两次交易，所以并不会影响总的交易次数。这种情况下的收益是local[i-1][j]+diff，diff=prices[i]-prices[i-1]。

2. 在(i-1)处买，在i处卖，得到的收益加上global[i-2][j-1]，就是local[i][j]可能的最大值。至于为什么不用再考虑其他的情况，比如说在(i-2)处买，在i处卖，这种情况相当于在(i-2)处买，在(i-1)处卖，在i处再卖。这种情况已经被case 1 cover了，所以无需再考虑。总之，在case 2，收益等于global[i-2][j-1]+diff。

所以，综合两种情况，递推关系应该如下，

local[i][j] = local[i-1][j] + diff

if (i-2 >= 0) local[i]][j] = max(local[i][j], global[i-2][j-1]+diff)

global[i][j] = max(global[i-1][j], local[i][j])

这道题的思路其实还是主要源于各位大牛的博客，只是我实在理解不了其中的一个递推关系，所以在这里写下了自己的思路。

1:  public class Solution {  
2:    public int maxProfit(int k, int[] prices) {  
3:      if (k < 1 || prices.length <= 1)  
4:        return 0;  
5:      if (k >= prices.length/2)  
6:        return helper(prices);  
7:      int[][] local = new int[prices.length][k+1];  
8:      int[][] global = new int[prices.length][k+1];  
9:      for(int i = 1; i < prices.length; i++) {  
10:        for(int j = 1; j <= k; j++) {  
11:          int diff = prices[i] - prices[i-1];  
12:          local[i][j] = local[i-1][j]+diff;  
13:          if(i-2 >= 0)  
14:            local[i][j] = Math.max(local[i][j], global[i-2][j-1]+diff);  
15:          global[i][j] = Math.max(global[i-1][j], local[i][j]);  
16:        }  
17:      }  
18:      return global[prices.length-1][k];  
19:    }  
20:    public int helper(int[] prices) {  
21:      int profit = 0;  
22:      for(int i = 1; i < prices.length; i++) {  
23:        profit += Math.max(prices[i]-prices[i-1], 0);  
24:      }  
25:      return profit;  
26:    }  
27:  }