链接

A. Functions again

题意

这是一道求最大连续子序列和变形题。

做法

先将abs(a[i+1]-a[i]算出来，然后用两个数组dp[i]，cp[i]，dp维护其最大值，cp维护其最小值，然后一直更新，复杂度O(n)，感谢wc

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 100010;

int main() {

    int n;

    LL a[maxn];

    LL dp[maxn], cp[maxn];

    while(cin >> n) {

        for (int i = 0; i < n; i++)

            cin >> a[i];

        for(int i = 0; i < n; i++)

            a[i] = abs(a[i + 1] - a[i]);

        LL ans = 0;

        for(int i = n - 2; i >= 0; i--) {

            dp[i] = max(a[i], a[i] - cp[i + 1]);

            cp[i] = min(a[i], a[i] - dp[i + 1]);

            ans = max(ans, dp[i]);

        }

        cout << ans << endl;

    }

}