leetcode309

使用动态规划，下面的代码可以通过210个测试，最后1个（第211个）会超时。说明思路是正确的，但是其中有一些是无效的计算。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n==0)
        {
            return 0;
        }
        int N=5000;
        int **D;
        D = new int*[N];
        for(int i=0;i<n;i++){
            D[i]=new int[N];
        }
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                int pj=prices[j];
                int pi=prices[i];
                D[i][j]=pj-pi;
            }
        }
        
        for(int len=1;len<n;len++){
            for(int i=0;i<n-1;i++){
                int j=i+len;
                if(j>=n){
                    break;
                }
                int m_ij=D[i][j];
                int max_k=0;
                for(int k=i+1;k<j;k++){
                    int m11 = D[i][k];
                    int m12=0;
                    if(k+2<j){
                        m12=D[k+2][j];
                    }
                    int m1=m11+m12;
                    
                    int m21=D[k][j];
                    int m22=0;
                    if(k-2>i){
                        m22=D[i][k-2];
                    }
                    int m2=m21+m22;
                    int m=max(m1,m2);
                    max_k=max(max_k,m);
                }
                D[i][j]=max(m_ij,max_k);
            }
        }
        
        return D[0][n-1];
    }
};

再提供网上AC的参考实现：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() <= 1)
            return 0;
        int s0 = 0;
        int s1 = -prices[0];
        int s2 = INT_MIN;
        for (int i = 1; i < prices.size(); i++){
            int pre0 = s0;
            int pre1 = s1;
            int pre2 = s2;
            s0 = max(pre0, pre2);
            s1 = max(pre0 - prices[i], pre1);
            s2 = pre1 + prices[i];
        }
        
        return max(s0, s2);
    }
};

再补充一个：

 1 class Solution {
 2 public:
 3     int maxProfit(vector<int>& prices) {
 4         int len = prices.size();
 5         if(len == 0 || len == 1)
 6             return 0;
 7         if(len == 2)
 8             return prices[1] > prices[0] ? prices[1] - prices[0] : 0;
 9         
10         vector<int> s0(len);
11         vector<int> s1(len);
12         vector<int> s2(len);
13         s0[2] = 0;
14         s1[2] = max(-prices[1], -prices[0]);
15         s2[2] = prices[1] - prices[0];
16         for(int i = 3; i < len; i++)
17         {
18             s0[i] = max(s0[i-1], s2[i-1]);
19             s1[i] = max(s0[i-1] - prices[i-1], s1[i-1]);
20             s2[i] = s1[i-1] + prices[i - 1];
21         }
22         return max(max(s0[len-1], s2[len-1]), s1[len-1] + prices[len-1]);
23     }
24 };