给定一个整数数组,如何找到两个索引i和j,以使子索引中的索引开始和结束的元素总和最大化,线性为时间?以int为单位的最大总和的子序列
回答
从我的programming pearls副本:
maxsofar = 0
maxendinghere = 0
for i = [0, n)
/* invariant: maxendinghere and maxsofar are accurate
are accurate for x[0..i-1] */
maxendinghere = max(maxendinghere + x[i], 0)
maxsofar = max(maxsofar, maxendinghere)
一个正确和简洁的。但它花了你同时把它复制下来,因为我设计它:) – 2009-11-10 09:39:59
Soooo,那么'我'和'j'是什么? – 2009-11-10 12:33:43
要获得序列的开始和结束,您只需要记住正确的i(ndex到数组中),具体取决于您在两个max语句中选择的内容。 – 2009-11-10 13:41:47
很简单。假设你得到了数组a
。首先,你计算阵列s
,其中s[i] = a[0]+a[1]+...+a[i]
。你可以做到这在线性时间:现在
s[0]=a[0];
for (i=1;i<N;i++) s[i]=s[i-1]+a[i];
,总和a[i]+a[i+1]+..+a[j]
等于s[j]-s[i-1]
。对于固定的j
,要最大化这种差异的值,您应该在0..(j-1)
范围内找到最小的。
想象一下在数组中寻找最小值的常用算法。
min = x[0];
for (j=1; j<N; j++)
if (x[j] < min)
min = x[j];
您迭代,每个数组元素比较min
...但在每次迭代这min
是数组,其中索引范围是0..j
最低值!这就是我们正在寻找的!
global_max = a[0];
max_i = max_j = 0;
local_min_index = 0;
for (j=1; j<N; j++){
// here local_min is the lowest value of s[i], where 0<=i<j
if (s[j] - s[local_min_index] > global_max) {
global_max = s[j] - s[local_min_index]
//update indices
max_i = local_min_index + 1;
max_j = j;
}
//update local_min_index for next iteration
if (s[j]<local_min){
local_min = s[j];
// update indices
local_min_index = j;
}
}
感谢匿名用户为他的冗长帖子解释代码中的错误。我摆脱了它们,除了如果'N == 0'失败。 – 2013-03-29 22:46:28
这个Python代码返回序列的边界。根据原来的问题,i=bestlo
,j=besthi-1
。
#
# given a sequence X of signed integers,
# find a contiguous subsequence that has maximal sum.
# return the lo and hi indices that bound the subsequence.
# the subsequence is X[lo:hi] (exclusive of hi).
#
def max_subseq(X):
#
# initialize vars to establish invariants.
# 1: best subseq so far is [bestlo..besthi), and bestsum is its sum
# 2: cur subseq is [curlo..curhi), and cursum is its sum
#
bestlo,besthi,bestsum = 0,0,0
curlo,curhi,cursum = 0,0,0
for i in xrange(len(X)):
# extend current subseq and update vars
curhi = i+1
cursum += X[i]
if cursum <= 0:
#
# the current subseq went under water,
# so it can't be usefully extended.
# start fresh at next index.
#
curlo = curhi
cursum = 0
elif cursum > bestsum:
# adopt current subseq as the new best
bestlo,besthi,bestsum = curlo,curhi,cursum
return (bestlo,besthi)
下面是这段代码通过的一些doctest示例。
r'''
doctest examples:
>>> print max_subseq([])
(0, 0)
>>> print max_subseq([10])
(0, 1)
>>> print max_subseq([-1])
(0, 0)
>>> print max_subseq(xrange(5))
(1, 5)
>>> print max_subseq([-1, 1, -1])
(1, 2)
>>> print max_subseq([-1, -1, 1, 1, -1, -1, 1, 2, -1])
(6, 8)
>>> print max_subseq([-2, 11, -4, 13, -5, -2])
(1, 4)
>>> print max_subseq([4, -3, 5, -2, -1, 2, 6,-4])
(0, 7)
'''
你真正需要Kadane的算法变更该记住的下限和上限为子阵列,这里的C++代码11:
#include <iostream>
#include <vector>
typedef std::pair<std::vector<int>::iterator, std::vector<int>::iterator> SubSeq;
SubSeq getMaxSubSeq(std::vector<int> &arr) {
SubSeq maxSequence{arr.begin(), arr.begin()};
auto tmpBegin = arr.begin();
int maxEndingHere = 0;
int maxSoFar = 0;
for(auto it = arr.begin(); it < arr.end(); ++it) {
int currentSum = maxEndingHere + *it;
if(currentSum > 0) {
if(maxEndingHere == 0) {
tmpBegin = it;
}
maxEndingHere = currentSum;
} else {
maxEndingHere = 0;
}
if(maxEndingHere > maxSoFar) {
maxSoFar = maxEndingHere;
maxSequence.first = tmpBegin;
maxSequence.second = it + 1;
}
}
return maxSequence;
}
int main()
{
std::vector<int> arr{-1, 2, 90, -50, 150, -300, 56, 12};
auto seq = getMaxSubSeq(arr);
while(seq.first != seq.second) {
std::cout << *(seq.first) << " ";
++(seq.first);
}
return 0;
}
- 1. 最大总和子列表?
- 2. 返回最大子列表的总和
- 3. x元素的最大连续子序列总和
- 4. 最大的二维子集和总和
- 5. 子阵最大总和
- 6. 查找最大总和子列表和总结分而治之
- 7. 确定最大总和的行和列
- 8. 查找2D numpy的阵列最大总和的位置
- 9. Hive中列的总和的最大值
- 10. 最小/最大 “总和” 的
- 11. 长度和最长增加的子序列的总和
- 12. 查找最大连续子序列总和的开始和结尾
- 13. 最大的连片子阵的总和大小不大于k
- 14. 连续子序列的最大和为零?
- 15. 作为int [](Java)int [] []行的总和
- 16. 非重叠连续子阵列的最大长度总和
- 17. 找到所有子阵列中最大值的总和
- 18. 以字节为单位确定缓冲区的总大小
- 19. 以KB/MB为单位的大小,仅最大。逗号后的2位数
- 20. 最大和最小总和
- 21. 三个序列的最长公共子序列int
- 22. 产品的最大总和
- 23. SQL中的最大总和
- 24. 以div为单位的最大宽度的中心图像
- 25. 从多个递增序列中选择最大值的总和
- 26. 最小长度L(递归)的最大连续子序列和
- 27. int扫描器可以使用的最大位数
- 28. num + den-1/num最大单位因子
- 29. 以毫秒为单位的TImespan,以分钟和秒为单位
- 30. 以周为单位的当前和上一年运行总计
你的意思是 - 指数之间? – Vladimir 2009-11-10 09:06:21
'i = 0'和'j = array.length-1' :) – 2009-11-10 09:08:25
@Bart,谁说数组元素大于零? – 2009-11-10 09:09:28