arrays - Kadane 的算法是否适用于运行长度编码的整数数组？

Question

假设 max_sequence(Array A): 是 Kadane 算法的解决方案。

你有一个数组：5,-3,-4,8,-1,12,-6,+4,+4,-14,+2,+8

你把这个数组缩短为正负序列的条纹：

所以现在数组是：+5,-7+8,-1,+12,-6,+8,-14+10

两个数组返回的最大序列相同。

你能否从数学上证明存在/不存在从函数 max_sequence 返回不同输出的整数序列（至少包含一个正整数）？

Answer 1

如果 max_sequence 包含正值的连续子序列中的一个正值，则它包含所有连续的正值，否则它将不是最大的。[减少荒谬]

如果 max_sequence 包含负值的连续子序列中的负值之一，则它包含所有连续的负值以及封闭的正值及其所有正后继或前驱，否则它将不是最大的。[减少荒谬]

因此，游程编码版本产生与非游程编码版本相同的结果。