3、前缀后缀数组

题目：

风口之下，猪都能飞。当今中国股市牛市，真可谓“错过等七年”。 给你一个回顾历史的机会，已知一支股票连续n天的价格走势，以长度为n的整数数组表示，数组中第i个元素（prices[i]）代表该股票第i天的股价。 假设你一开始没有股票，但有至多两次买入1股而后卖出1股的机会，并且买入前一定要先保证手上没有股票。若两次交易机会都放弃，收益为0。 设计算法，计算你能获得的最大收益。 输入数值范围：2<=n<=100,0<=prices[i]<=100

输入例子:

3,8,5,1,7,8

输出例子:

12

思路：

1、动态规划

i表示第i天，k表示第k次交易

• 状态转移方程：
  • pmax = max{ f(j,k-1)+prices[i]-prices[j] } (0<=j<i)}
  • f(i,k) = max{ f(i-1,k), pmax}
  • 即f(i,k ) = max{  f(i-1,k) ,  max { f(j,k-1) + prices[i]-prices[j]  |  0<=j<i } }
• f(i-1,k)表示第i天不交易
• max{ f(j,k-1)+prices[i]-prices[j] } (0<=j<i)}表示第i天卖，而这次交易的买应该来自第j天，f(j,k-1) +prices[i] - prices[j] ，0<=j<i ，取最大值。
• max{ f(j,k-1)+prices[i]-prices[j] } (0<=j<i)}，这一步可以通过单调队列来优化，可以参考一下：，简单的来说，就是将方程中包含j的部分单独拿出来处理，即max(f(j,k-1)-prices[j])

2、前缀、后缀数组

通过前缀数组A来计算0次或1次交易的最大收益；

通过后缀数组B来计算0次或1次交易的最大收益；

通过遍历0-n，计算max(A[i]+B[i])即为最大收益；

代码：

1、简单的动态规划

class Solution {public:    /**     * 计算你能获得的最大收益     *      * @param prices Prices[i]即第i天的股价     * @return 整型     */    int kTransaction(vector
     
       prices,int k){        int n=prices.size();        vector
      
       
         > dp(n,vector
        
         (k+1,0));        int mx;        for(int i=1;i
         
          =0;j--)                    mx=max(mx,dp[j][t-1]+prices[i]-prices[j]);                dp[i][t]=mx;            }        }        return dp[n-1][k];    }         int calculateMax(vector
          
            prices) { return kTransaction(prices,2); }};
          
         
        
       
      
     

2、单调队列优化的动态规划

class Solution {public:    /**     * 计算你能获得的最大收益     *      * @param prices Prices[i]即第i天的股价     * @return 整型     */    int kTransaction(vector
     
       prices,int k){        int n=prices.size();        vector
      
       
         > dp(n,vector
        
         (k+1,0));        vector
         
           pMax(k+1,0);        int mx;        for(int i=0;i<=k;i++)            pMax[i]=-prices[0];        for(int i=1;i
          

prices) { return kTransaction(prices,2); }};