题目描述

看题解都是使用二维数组。没听课，直接过来敲的。
可能跟正常的理解不一样。

首先你需要看懂题目，然后请先看一下下面的代码：

超时代码

/*****************************************
Problem Name  : 
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
int a[N],b[N],c[N];
int main()
{
    int n;
    cin >> n;
    for(int i = 2 ; i <= n+1 ; i++)
    {
        int x;
        cin >> x;
        a[i] = x;
        b[i] = b[i-1];
        for(int j = i - 1  ; j >= 2 ; j--)
        {
            b[i] = max(b[i] , a[i] - a[j] + b[j-2] );
        }
    }
    cout << b[n+1] << endl;
}

AC第一个代码

这个代码是上一个代码的优化

/*****************************************
Problem Name  : 
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
int a[N],b[N],c[N];
int main()
{
    int n;
    cin >> n;
    int maxx = -999990;
    for(int i = 2 ; i <= n+1 ; i++)
    {
        cin >> a[i];
        maxx = i > 3 ? max(b[i-3] -  a[i-1] , maxx) : max(maxx, 0 - a[i]); // 前i-1个当中的最值。 i-1当中，买掉当前能够得到的最值。
        b[i] = i > 2 ? max(b[i-1] ,a[i] + maxx) : b[i-1];
    }
    cout << b[n+1] << endl;
}

AC C++ 代码 这个代码是在上面AC代码上优化的

/*****************************************
Problem Name  : 若需要详细的推理过程，请私信我，我补充代码解释。
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
int f[N];
int main()
{
    int n;
    cin >> n;
    int maxx = -0x3f3f;
    for(int i = 1,x,s ; i <= n ; i++)
    {
        cin >> x;
        maxx = i > 2 ? max(f[i-3] - s , maxx) : max(maxx, 0 - x); 
        f[i] = i > 1 ? max(f[i-1] , x + maxx) : f[i-1];
        s = x ;
    }
    cout << f[n] << endl;
}