作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我们有this在 O(n) 时间内在给定序列中找到最大正子序列的算法。谁能提出类似的算法来寻找最小正连续子序列。
例如 如果给定的序列是 1,2,3,4,5,答案应该是 1。 [5,-4,3,5,4] ->1 是元素 [5,-4] 的最小正和。
最佳答案
不可能有这样的算法。这个问题的下限是 O(n log n)。我将通过减少 element distinctness problem 来证明这一点到它(实际上是它的非负变体)。
假设我们有一个 O(n) 算法来解决这个问题(最小非负子数组)。
我们想知道一个数组(例如 A=[1, 2, -3, 4, 2])是否只有不同的元素。为了解决这个问题,我可以构造一个包含连续元素之间差异的数组(例如 A'=[1, -5, 7, -2])并运行我们拥有的 O(n) 算法。当且仅当最小非负子数组大于 0 时,原始数组才具有不同的元素。
如果我们有一个 O(n) 算法来解决您的问题,我们就会有一个 O(n) 算法来解决元素差异性问题,我们知道这在图灵机上是不可能的。
关于algorithm - 如何在 O(n) 时间内找到最小正连续子序列?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31640902/
我是一名优秀的程序员,十分优秀!