一. 题目

二. 思路

1. 思路1

2. 思路2

三. 代码

1. 思路1

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10, M=3, INF=2e9;

int n;
int a[N];

class DP
{
public:
    int f[N][M];

public:
    DP()
    {
        initIO();
    }

    void initIO()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr), cout.tie(nullptr);
    }

    void init()
    {
        fill(&f[0][0], &f[0][0]+N*M, -INF);
        f[0][2]=0;
    }

    int work()
    {
        for(int i=1;i<=n;++i)
        {
            f[i][0]=max(f[i-1][0], f[i-1][2]-a[i]);
            f[i][1]=f[i-1][0]+a[i];
            f[i][2]=max(f[i-1][1], f[i-1][2]);
        }
        return max(f[n][1], f[n][2]);
    }
}dp;

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    dp.init();
    cout<<dp.work();
}

2. 思路2

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10, M=3, INF=2e9;

int n;
int a[N];

class DP
{
public:
    int f[N][M];

public:
    DP()
    {
        initIO();
    }

    void initIO()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr), cout.tie(nullptr);
    }

    void init()
    {
        fill(&f[0][0], &f[0][0]+N*M, -INF);
        f[0][0]=0;
    }

    int work()
    {
        for(int i=1;i<=n;++i)
        {
            f[i][0]=max(f[i-1][0], f[i-1][2]);
            f[i][1]=max(f[i-1][1], f[i-1][0]-a[i]);
            f[i][2]=f[i-1][1]+a[i];
        }
        return max(f[n][0], f[n][2]);
    }
}dp;

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    dp.init();
    cout<<dp.work();
}