algorithm - 阵列中最深坑的困惑

Question

我把这个问题作为面试的先决条件，

A non-empty zero-indexed array A consisting of N integers is given. A pit in this array is any triplet of integers (P, Q, R) such that: 0 ≤ P < Q < R < N;

sequence [A[P], A[P+1], ..., A[Q]] is strictly decreasing, i.e. A[P] > A[P+1] > ... > A[Q];

sequence A[Q], A[Q+1], ..., A[R] is strictly increasing, i.e. A[Q] < A[Q+1] < ... < A[R].

The depth of a pit (P, Q, R) is the number min{A[P] − A[Q], A[R] − A[Q]}. For example, consider array A consisting of 10 elements such that:

A[0] =  0
A[1] =  1
A[2] =  3
A[3] = -2
A[4] =  0
A[5] =  1
A[6] =  0
A[7] = -3
A[8] =  2
A[9] =  3

Triplet (2, 3, 4) is one of pits in this array, because sequence [A[2], A[3]] is strictly decreasing (3 > −2) and sequence [A[3], A[4]] is strictly increasing (−2 < 0). Its depth is min{A[2] − A[3], A[4] − A[3]} = 2.

Triplet (2, 3, 5) is another pit with depth 3.

Triplet (5, 7, 8) is yet another pit with depth 4. There is no pit in this array deeper (i.e. having depth greater) than 4.

它表示 Triplet (5, 7, 8) 的最深坑深度为 4。

但是Triplet(2, 7, 9)不是最深的坑深6吗？

Triplet (2, 7, 9) 对应的值为(3, -3, 3) 也满足上述条件，即

1) 0 ≤ P < Q < R < N
2) A[P] > A[P+1] > ... > A[Q] and A[Q] < A[Q+1] < ... < A[R]

所以在这种情况下，min{A[P] − A[Q], A[R] − A[Q]} 是 6。

我在这里错过了什么？

P.S. 如果您认为这篇帖子不属于这个论坛的这里，那么请指出我应该在哪里发布它。

Answer 1

请参阅 P 中的序列至 Q对于 2 to 7 .

是3 -2 0 1 0 -3 .

sequence [A[P], A[P+1], ..., A[Q]] is strictly decreasing, i.e. A[P] > A[P+1] > ... > A[Q];

规则说这应该是一个递减序列。但事实并非如此。 3>-2但是-2 is not greater than 0 . 此处顺序中断。

来自 7 to 9 .没问题，因为序列在增加。 -3<2<3 .