股票买卖

a[i]表示股票第i天的价格，1<=i<=n

至多进行一次交易

//p[i]表示1~i内交易的最高收益
p[1]=0;
for(int i=2,minv=a[1];i<=n;i++)
{
    p[i]=max(p[i-1],a[i]-minv);
    minv=min(minv,a[i]);
}

//可简化为
for(int i=2,profit=0,int minv=a[1];;i<=n;i++)
{
    profit=max(profit,a[i]-minv);
    minv=min(minv,a[i]);
}
profit为最高的收益

至多两次交易

//p[i]前1~i天买卖一次股票的最大收益
pre[1]=0;
for(int i=2,minv=a[1];i<=n;i++)
{
    pre[i]=max(pre[i-1],a[i]-minv);//第i天卖
    minv=min(minv,a[i]);
}
back[n]=0;
for(int j=n-1,max=a[n];j>=1;j--)
{
    back[j]=max(pre[j+1],maxv-a[j]);//第j天买
    maxv=max(maxvv,a[j]);
}
int res=0;
for(int i=0;i<=n;i++)
    res=max(res,pre[i]+back[i+1]);

进行k次交易

状态0表示手中无股票
状态1表示手中有股票
f[i][j][k]表示目前遍历到第i天，完成了j次交易，k=0手中无股票，k=1手中有股票
买入股票->卖出股票，算一次完整交易,买入股票支付a[i]元，卖出股票收入a[i]元

memset(f,-0x3f,sizeof f);
f[0][0][0]=0;
for(int i=1;i<=n;i++)
    for(int j=0;j<=k;j++)
    {
        f[i][j][0]=f[i-1][j][0];//f[i-1][j][0],手里没股票且没有买入股票
        if(j>0)
        f[i][j][0]=max(f[i][j][0],f[i-1][j-1][1]+a[i])//f[i-1][j-1][1]+a[i],以a[i]价格卖出，完成一次交易
        f[i][j][1]=max(f[i-1][j][1],f[i-1][j][0]-a[i]);
        //f[i-1][j][1]，手上有股票，没有卖出
        //f[i-1][j][0]-a[i]，以a[i]价格买入后，手上有一支股票
    }