CodeForces 789C—Functions again——算法笔记

题目描述：

Something happened in Uzhlyandia again… There are riots on the streets… Famous Uzhlyandian superheroes Shean the Sheep and Stas the Giraffe were called in order to save the situation. Upon the arriving, they found that citizens are worried about maximum values of the Main Uzhlyandian Function f, which is defined as follows:

In the above formula, 1 ≤ l < r ≤ n must hold, where n is the size of the Main Uzhlyandian Array a, and |x| means absolute value of x. But the heroes skipped their math lessons in school, so they asked you for help. Help them calculate the maximum value of f among all possible values of l and r for the given array a.

输入：

The first line contains single integer n (2 ≤ n ≤ 105) — the size of the array a.
The second line contains n integers a1, a2, …, an (-109 ≤ ai ≤ 109) — the array elements.

输出：

Print the only integer — the maximum value of f.

输入输出样例：

题目大意：就是找到 f (l, r) 的最大值。观察 f (l, r) 是由相邻两个数相减去取绝对值再变符号相加得来。
举个例子：比如样例一：f (1, 5) = 3 + (-2) + 1 + (-2) .但最终要求的是 f (l , r) 的最大值。这就和求最大连续子段和一样了，表示有模板可以套了。高兴！！！ 观察一下，好像这个里面最大值是 f (1, 1) = 3. 但是，要注意的是，从 1 开始整理数组得到的是上面的结果，当从 2 开始整理数组结果就不一样了。请看：f (2, 5) = 2 + (-1) + 2 . 说明，整理后的数组有两种情况。这是由于 (-1)^(i-l) 决定的。因此，就要分别把两种数组都求出来，然后再分别求两个数组的最大连续子段和，再比较求出字段和大的那一个就是答案。

参考代码：

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;

#define INF 0x3f3f3f
#define ll long long
#define clean(arrays) memset(arrays, 0, sizeof(arrays))

ll Max_Sum(ll *a, int n)
{
    ll index = 0, sum = -9999;
    for (int i = 1; i <= n; i++)
    {
        if (index <= 0)
            index = a[i];
        else
            index += a[i];
        if (index > sum)
            sum = index;
    }
    return sum;
}

const int MAX_NUM = 1e5 + 5;
ll a[MAX_NUM], b[MAX_NUM];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i < n; i++) {	//从起始开始计算，然后求其中的最大子段和
        a[i] = abs(a[i] - a[i + 1]);
        if (i % 2 == 1)				// i 是奇数 结果为正
            a[i] = a[i];
        else						// i 是偶数 结果为负
            a[i] = -a[i];	
        b[i] = -a[i];       		// 存储与 a 数组相反的那一组数
    }
    ll back1 = Max_Sum(a, n - 1);
    ll back2 = Max_Sum(b, n - 1);
    ll result = max(back1, back2);
    cout << result << endl;
    return 0;
}