algorithm - 包含结果数组的最大和最小元素的最大子数组数

Question

您将获得一个包含 n 个元素的数组，您可以从提供的数组中删除最多一个元素。元素的顺序保持不变。您需要最大化包含结果数组的最大和最小元素的子数组的数量。子数组是数组的连续元素的序列 输入 T 测试用例的编号 N 数组的大小 N 数组元素 输出 对于每个测试用例，打印一个整数，包含结果数组的最大和最小元素的子数组的最大数量示例

4

6

7 2 5 4 3 1

7

1 2 3 4 5 6 7

6

2 5 3 2 5 5

4

5 5 5 5

输出

4

1

12

15

测试用例 1 解释如果我们从数组中删除 1，那么结果数组将是 7 2 5 4 3 所以子数组的数量将包含最大 7 和最小 2 将是 4

[7,2]

[7,2,5]

[7,2,5,4]

[7,2,5,4,3]

标签： algorithmdata-structures

Answer 1

做一些数学。如果 min 和 max 元素位于索引i和j（与谁在哪里无关，只是i < j），则子数组的数量为(i + 1) * (len - j)。证明这个事实，或者至少说服自己确实如此。

现在，证明（或至少说服自己）删除除 min 或 max 之外的任何元素是没有意义的。

我希望这足以让你开始。