Kadane 算法是否适用于运行长度编码整数数组?



假设max_sequence(数组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返回不同的输出?

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

如果max_sequence包含负值的连续子序列中的一个负值,则它包含所有连续的负值以及封闭的正值及其所有正后继值或前置值,否则它不是最大值。[归纳荒谬]

因此,运行长度编码版本与非运行长度编码版本产生相同的结果。

最新更新