c - 如何为遵循下面提到的标准的每个索引找到左子数组和右子数组？

Question

存在一个序列问题，其中对于每个索引i 在数组中我们定义了两个量。

让 r 是最大索引，使得<强> r>=i 和来自 i 的子数组 至 r (含)是非递减或非递增。

让 l 是满足 l<=i 的最小索引 和来自 l 的子数组 到 i(含)是非递减或非递增。

现在，我们定义索引的点 i 等于

<强> max(|Ai−Al|,|Ai−Ar|) 。

请注意l和r每个索引可以不同。

问题的任务是找到数组A的索引其中得分最高。

我的逻辑:

1. 首先扫描数组中的所有元素。

2. 对于每个索引，找到遵循递增或递减序列的 l 和 r，然后计算该索引的最大点。

我的问题是，这需要 O(N^2)时间。

这个问题能在更短的时间内完成吗？

Answer 1

两个连续的相同数字具有相同的点，并且不影响任何其他点的点，因此可以假设这种情况不存在。

因此，考虑一个没有连续相同数字的输入数组 a，可以假设子序列中最长的非减或非增序列为 [0, I1] [I1, I2] ... [Ix, n - 1]，表示为按索引，n 是数组的长度。每个递减子序列后面跟着一个递增子序列，反之亦然。

对于任何 Ii，索引为 Ii 的点的点等于 max(|AIi - AI(i - 1)|, |AIi - AI(i + 1)|)。 Ii 和 I(i + 1) 之间的任何索引都小于 Ii 和 I(i + 1) > 并且不必考虑。

所以我们只需要找出所有AIi和AI(i + 1)之间的最大值即可。

经过大量的尝试，我的程序终于被接受了(主要是因为两个int 32之间的差异不一定在有符号的int 32范围内)，代码如下。

#include <stdio.h>

#define MAXN 200002
long long a[MAXN];

long long abs(long long n)
{
    if (n >= 0)
        return n;
    return -n;
}

long long find_score(int size)
{
    int i = 0;
    long long maximum_score = 0;
    while (i < size - 1)
    {
        //Jump over consecutive indentical numbers
        while (a[i + 1] == a[i])
        {
            if (i < size - 1)
                i++;
            else
                break;
        }
        int j = i + 1;
        int inc_or_dec = a[j] > a[i];
        while (j < size - 1 && (!((a[j + 1] > a[j]) ^ inc_or_dec) || a[j + 1] == a[j]))j++;
        if (abs(a[j] - a[i]) > maximum_score)
            maximum_score = abs(a[j] - a[i]);
        i = j;
    }
    return maximum_score;
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        int num;
        scanf("%d", &num);
        for (int i = 0; i < num; i++)
        {
            scanf("%lld", a + i);
        }
        printf("%lld\n", find_score(num));
    }
    while (1);
    return 0;
}

很高兴知道我的代码中是否存在任何“实现定义”的问题。