一. 题目描述

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

二. 题目分析

这一题的难度要远高于前面几题，需要用到动态规划，代码参考了博客：http://www.cnblogs.com/grandyang/p/4295761.html

这里需要两个递推公式来分别更新两个变量local和global，然后求至少k次交易的最大利润。我们定义local[i][j]为在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润，此为局部最优。然后我们定义global[i][j]为在到达第i天时最多可进行j次交易的最大利润，此为全局最优。它们的递推式为：

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

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

三. 示例代码

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; class Solution { public: int maxProfit(int k, vector
        
          &prices) { if(prices.empty() || k == 0) return 0; if(k >= prices.size()) return solveMaxProfit(prices); vector
         
           global(k + 1, 0); vector
          
            local(k + 1, 0); for(int i = 1; i < prices.size(); i++) { int diff = prices[i] - prices[i - 1]; for(int j = k; j >= 1; j--) { local[j] = max(local[j] + diff, global[j - 1] + max(diff, 0)); global[j] = max(global[j], local[j]); } } return global[k]; } private: int solveMaxProfit(vector
           
             &prices) { int res = 0; for(int i = 1; i < prices.size(); i++) { int diff = prices[i] - prices[i - 1]; if(diff > 0) res += diff; } return res; } };
           
          
         
        
       
      
     
    
   

?