Kadane算法能否用于游程编码整数数组？及等价性证明问题

问题2：是否存在至少包含一个正整数的整数序列，使得原数组与压缩后的数组的max_sequence输出结果不同？ #

结论是：不存在这样的序列。我们可以通过数学推导证明原数组和其正负段压缩数组的最大子数组和（即Kadane算法的输出）必然相等。

定义与前提

先明确几个核心概念：

• 原数组 ( A )：由整数组成，至少包含一个正整数。
• 压缩数组 ( B )：将 ( A ) 中连续的正整数段合并为该段的总和（记为 ( P_i > 0 )），连续的负整数段合并为该段的总和（记为 ( N_i < 0 )），最终得到一个正负交替的数组，形式为 ( [P_1, N_1, P_2, N_2, ..., P_k] ) 或 ( [N_1, P_1, N_2, P_2, ..., N_k] )。
• ( \text{max_sequence}(X) )：Kadane算法对数组 ( X ) 返回的最大子数组和。

推导过程

我们需要证明 ( \text{max_sequence}(A) = \text{max_sequence}(B) )，分两部分论证：

1. ( \text{max_sequence}(A) \leq \text{max_sequence}(B) )
   对于原数组 ( A ) 中的任意子数组 ( S )，其和有以下几种情况：

   • 如果 ( S ) 完全在某个正段 ( P_i ) 内：( S ) 的和是 ( P_i ) 的一部分，必然小于等于 ( P_i )（因为 ( P_i ) 是正整数的和，所有元素为正）。而 ( B ) 中 ( P_i ) 是单个元素，对应的子数组和就是 ( P_i )，因此 ( S ) 的和不会超过 ( B ) 中该元素的和。
   • 如果 ( S ) 完全在某个负段 ( N_i ) 内：( S ) 的和为负数，而 ( A ) 至少有一个正整数，因此 ( \text{max_sequence}(A) ) 必然是正数，这种子数组不可能是最大的。
   • 如果 ( S ) 跨越多个段（比如从 ( P_i ) 的一部分开始，经过 ( N_i, P_{i+1}, ... )，到 ( P_j ) 的一部分结束）：设 ( S ) 的和为 ( a + N_i + P_{i+1} + ... + N_{j-1} + b )（其中 ( 0 < a \leq P_i )，( 0 < b \leq P_j )）。而 ( B ) 中对应完整段的子数组和为 ( P_i + N_i + P_{i+1} + ... + P_j = (a + (P_i - a)) + N_i + ... + (b + (P_j - b)) = S_{\text{和}} + (P_i - a + P_j - b) )。由于 ( P_i - a \geq 0 )、( P_j - b \geq 0 )，且至少有一个大于0（否则 ( S ) 就是完整段的子数组），因此 ( B ) 中该子数组的和必然大于等于 ( S ) 的和。
   • 其他跨越情况（比如从负段开始或结束）：这类子数组的和必然小于某个正段的和，不可能成为最大子数组。

2. ( \text{max_sequence}(B) \leq \text{max_sequence}(A) )
   ( B ) 中的任意子数组，对应的是 ( A ) 中若干个完整的正负段组成的连续子数组，其和与 ( A ) 中该子数组的和完全相等。因此 ( B ) 的最大子数组和不可能超过 ( A ) 的最大子数组和。

结合两部分推导，可得 ( \text{max_sequence}(A) = \text{max_sequence}(B) )，即不存在满足条件的整数序列，使得两者的输出结果不同。

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