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

Credits:

Special thanks to  for adding this problem and creating all test cases.

 

这题难度明显增大。是和两道题的结合。

参考，主要是两个递推公式。

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

1 class Solution { 2 public: 3     int maxProfit(int k, vector
     
      & prices) { 4         int result; 5         int total_times=0; 6         int profit_max = 0; 7         for(int i=1;i
      
       0)11             {12                 profit_max +=diff;13                 if(((i
       
        <=0))||(i==prices.size()-1))14                 {15                     total_times++;16                 }17             }18         }19         if(k>=total_times) return profit_max;20         vector
        
          local(k + 1, 0);21         vector
         
           global(k + 1, 0);22         for(int i = 1; i < prices.size(); i++) 23         {24             int diff = prices[i] - prices[i - 1];25             for(int j = k; j >= 1; j--) {26                 local[j] = max(local[j] + diff, global[j - 1] + max(diff, 0));27                 global[j] = max(global[j], local[j]);28             }29         }30         return global[k];31     }32 };