gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:54:33 26 4
gpt4 key购买 nike

假设 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 返回不同输出的整数序列(至少包含一个正整数)?

最佳答案

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

如果 max_sequence 包含负值的连续子序列中的负值之一,则它包含所有连续的负值以及封闭的正值及其所有正后继或前导,否则它不会是最大的. [归谬法]

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

关于arrays - Kadane 的算法是否适用于运行长度编码的整数数组?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49847337/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com