请解释下述伪代码功能，并说明输出中(9, -4)的合理性

问题背景 #

你运行一段旨在查找整数数组中峰值元素及其索引的伪代码后，得到输出 [(1, 4), (4, -9), (7, 12), (9, -4)]，但无法理解为何 (9, -4) 会出现在结果中。给定数组为：[1,4,2,-2,-9,10,2,12,2,-4,-4,-4,-4,2,6,7]，伪代码如下：

array[N] # array of N integers, indexed 0 to N-1;
# assume it’s populated with [1,4,2,-2,-9,10,2,12,2,-4,-4,-4,-4,2,6,7]
peak = array[0]
index = 0
output = [] # array of tuples
For x in 1..N-1
    if (array[x]*array[x-1] > 0)
       if peak < 0 and array[x] < peak
          peak = array[x]
          index = x
       if peak >= 0 and array[x] > peak
          peak = array[x]
          index = x

    else
       output.insert( (index, peak) )
       peak = array[x]
       index = x
end if
end for
return output

核心逻辑拆解 #

这段伪代码的实际逻辑并非传统意义上的"峰值"（比左右元素都大/小），而是按元素正负号分组处理：

• 当当前元素和前一个元素同号（乘积>0）时，在当前组内更新极值：正数组找最大值，负数组找最小值
• 当遇到正负号切换（乘积≤0）时，将当前组的极值存入输出列表，然后切换到新组

遍历过程分步解析 #

我们对应数组的索引和值，一步步走遍历流程：
数组索引与对应值：0:1, 1:4, 2:2, 3:-2,4:-9,5:10,6:2,7:12,8:2,9:-4,10:-4,11:-4,12:-4,13:2,14:6,15:7

1. 第一组（正数，索引0-2）：遍历到x=3时，元素-2与前一个元素2异号，将当前组最大值(1,4)加入输出，输出变为[(1,4)]
2. 第二组（负数，索引3-4）：遍历到x=5时，元素10与前一个元素-9异号，将当前组最小值(4,-9)加入输出，输出变为[(1,4),(4,-9)]
3. 第三组（正数，索引5-8）：遍历到x=9时，元素-4与前一个元素2异号，将当前组最大值(7,12)加入输出，输出变为[(1,4),(4,-9),(7,12)]
4. 第四组（负数，索引9-12）：遍历到x=13时，元素2与前一个元素-4异号，触发else分支，将当前组的最小值(9,-4)加入输出，输出变为[(1,4),(4,-9),(7,12),(9,-4)]
5. 最后一组（正数，索引13-15）：遍历结束后，伪代码没有处理最后一组的逻辑，因此这组的最大值不会被加入输出

结论 #

(9, -4) 来自数组中索引9到12的负数序列，当遍历到索引13的正数元素时，正负号发生切换，伪代码将该负数组的最小值（即-4，对应索引9）存入输出列表，所以它会出现在结果中。

内容的提问来源于stack exchange，提问作者Aman Raheja