当前位置: 首页 > 知识库问答 >
问题:

求子数组的最小绝对值和

黄磊
2023-03-14
A = [2, -4, 6, -3, 9]
|(−4) + 6 + (−3)| = 1 <- minimal absolute sum
complexity:
- expected worst-case time complexity is O(N*log(N))
- expected worst-case space complexity is O(N)

共有1个答案

鄂坚
2023-03-14

答案是肯定的,Kadane的算法绝对是解决你的问题的方法

http://en.wikipedia.org/wiki/maximum_subarray_problem

源码-我和一个博士生密切合作过,他的整个博士论文都致力于最大子数组问题。

 类似资料:
  • 我想从数组的一部分找到最大值和最小值。我知道我可以通过复制数组将所需的数组部分复制到另一个数组中,但只是想知道是否可以不复制数组,因为我必须为不同的子数组进行循环 例如: 现在我想从1到4找到子数组的最小/最大值(如果可能,不复制子数组)

  • 这是一个非常基本的算法(不能再简单了),但我被难住了。我们有一个元素数组,我们必须确定最小值和最大值。 通常的方法是遍历数组,找出最小值和最大值,即2n比较。 稍微有效的方法是首先对数组的连续元素进行比较,以确定任意两个元素的最大值和最小值(N/2比较)。我们现在有n/2 min和n/2 max元素。现在我们可以在n/2+n/2+n/2(前一步)=3/2*n或1.5n中得到最终的max和min 那

  • 今年Spring我为一家IT公司写了实习入学考试。下面描述了一个问题。我不能解决它,所以我需要帮助(目前我要通过新的测试,所以我需要分析我的错误)。我很乐意为你效劳。 输入:一个数组arr,N个整数,arr的N个长度,数字K(K 对于offset的所有容许值,求s_arr(offset)的最小元素 算法复杂度应小于O(n*k) 输出:所有对(偏移量,最小(s_arr(偏移量)) 我的微不足道的解决

  • 本节通过求数组的最大和最小值来提高初学者对数组的一些基本应用。 程序运行结果如下: 最高成绩:100 最低成绩:67 将变量 min 与 max 初值设成数组的第 1 个元素后,再逐一与数组中的各元素相比。比 min 小,就将该元索的值指定给 min 存放,使 min 的内容保持最小。同样,当该元素比 max 大时,就将该元素的值指定给 max 存放,使 max 的内容保持最大。for 循环执行完

  • 那么我如何使用这个pair类和我的方法来找到最小值和最大值。

  • 主要内容:普通算法,分治算法程序中,我们经常使用数组(列表)存储给定的线性序列(例如 {1,2,3,4}),那么如何查找数组(序列)中的最大值或者最小值呢? 查找数组(序列)中最大值或最小值的算法有很多,接下来我们以 {3,7,2,1} 序列为例讲解两种查找最值的算法,一种是普通算法,另一种是借助 分治算法解决。 普通算法 普通算法的解决思路是:创建两个变量 max 和 min 分别记录数组中的最大值和最小值,它们的初始值都