算法

(dp)

时间复杂度

O(n)

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int m,n;
int w[100010],f[100010][2];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];
    f[1][0]=0;//f表示第i天持股情况  0未持股  1持股
    f[1][1]=w[1]*-1;//f[1][1]表示第一天持股  则收益为第一天股价的负数
     for(int i=2;i<=n;i++)
    {
        f[i][0]=max(f[i-1][0],f[i-1][1]+w[i]);
        f[i][1]=max(f[i-1][1],f[i-1][0]-w[i]);
    }
    cout<<f[n][0]<<endl;//结果为最后一天不持股的情况
    return 0;
}