求助|力扣53题如何从穷举推导出Kadane算法?
404
1 天前
1 天前
发布于 重庆

大家好,我在刷题的时候,总是忍不住寻找如何从穷举法中找到规律,从而推导出力扣官方题解。

我之所以痴迷于从穷举法中推导规律,是因为我曾经听过一句话,“所有的数据结构都是数组和链表,所有的算法都是空间换时间,时间换空间”。

我将这句话视作算法的大一统理论。

因此,对每一道题目,我总是忍不住好奇,如何在只知道数组链表,以及提示中的工具(例如哈希表和双指针)的情况下,自己推导出官方的巧妙算法。

而53题我在推理时遇到一些疑惑🤨

1778915207-yjnrRM-1778915204229177.jpeg

已经知道可以用双循环完成穷举算法。但是,在我已知穷举的情况下,我该如何推导出Kadane算法呢?

顺带一提,我在这个题目的时候,第一反应是先遍历一遍整个数组,然后问自己,在一次遍历就能得到数组下标和值的情况下,能否推理如何得到Kadane算法。

评论 (5)