题解 | #股票交易的最大收益（二）#

经典DP，直接写最多允许k次交易的算法

j=1,3,5,7.....2k+1 手中无股
f[i][j] 表示前i天（第i-1天结束）处于阶段j的最大收益
f[i][j]=max(f[i-1][j],f[i-1][j-1]+p[i-1]-p[i-2])

j=2,4,6,.....2k 持股
f[i][j]=max(f[i-1][j]+p[i-1]-p[i-2],p[i-1][j-1],f[i-1][j-1]+p[i-1]-p[i-2])

int maxProfit(vector<int>& prices) {
        // write code here
        int f[200010][5];//此处k为2
        int inf=0x3f3f3f3f;
        int k=5;
        int n=prices.size();
        memset(f,0,sizeof(f));
        f[0][1]=0;
        for(int i=2;i<=k;i++)
        {
            f[0][i]=-inf;
        }
        int ans=-inf;
        for(int i=1;i<=n;i++)
        {
            //奇数
            //f[i][j]=max(f[i-1][j],f[i-1][j-1]+prices[i-1]-prices[i-2]);
            for(int j=1;j<=k;j+=2)
            {
                f[i][j]=f[i-1][j];
                if(i>1&&j>1&&f[i-1][j-1]!=-inf)
                {
                    f[i][j]=max(f[i][j],f[i-1][j-1]+prices[i-1]-prices[i-2]);
                }
                //ans=max(ans,f[i][j]);
            }

//f[i][j]=max(f[i-1][j-1],f[i-1][j]+prices[i-1]-prices[i-2],f[i-1][j-2]+prices[i-1]-prices[i-2]);
            for(int j=2;j<=k;j+=2)
            {
                f[i][j]=f[i-1][j-1];

                if(i>1&&f[i-1][j]!=-inf)
                {
                    f[i][j]=max(f[i][j],f[i-1][j]+prices[i-1]-prices[i-2]);
                }
                if(i>1&&j>2&&f[i-1][j-2]!=-inf)
                    f[i][j]=max(f[i][j],f[i-1][j-2]+prices[i-1]-prices[i-2]);
                //ans=max(ans,f[i][j]);
            }
        }
        for(int i=1;i<=k;i+=2)
        {
            ans=max(ans,f[n][i]);
        }
        return ans;
    }
}