如何根据下面提到的标准为每个索引找到左侧和右侧的子阵列？

Question

存在序列问题，其中对于阵列中的每个索引 i我们定义两个量。

让r是最大索引使得 r>=i和子阵列从i到r（含）是要么不降低或不提高。

让l是最小索引使得l<=i和子阵列从l到我（含）是要么不降低或不提高。

现在，我们定义了一个指数i点等于

max(|Ai−Al|,|Ai−Ar|)。

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

该问题的任务是找到具有最大点的数组A的索引。

我的逻辑：

1. 第一扫描中的阵列中的所有元件。

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

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

问题可以在更短的时间内完成吗？

Answer 1

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

所以考虑一个输入阵列的不具有连续的相同号码，则可以假设没有最长递减或子序列没有增加是[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之间的差别不一定是一个有符号整数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; 
} 

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