最大和子数组 O(n) 不是 Kadane 的
Maximum Sum Subarray O(n) not Kadane's
我正在读 Cormen 的 "Introduction to Algorithms"。
对于最大和子数组问题的线性算法,我提出了自己的解决方案。在实施之前没有检查现有的(Kadena 的)。
现在我正在用不同的测试场景对其进行测试,结果总是比嘉手纳的好。我不相信这样的运气,但找不到我错过的东西。你能看看它是否是一个可行的解决方案吗?
public void findMaxSubarray(Number[] numbers) {
int maxSum = Integer.MIN_VALUE;
int left = 0;
int right = numbers.length - 1;
int i = 0;
int j = i + 1;
int sum = numbers[i].intValue();
while (i < numbers.length) {
if (maxSum < sum) {
maxSum = sum;
left = i;
right = j - 1;
}
if (j >= numbers.length)
return;
sum = sum + numbers[j].intValue();
if (sum <= 0) {
// ignoring "first" negative numbers. shift i to first non-negative
while (numbers[j].intValue() <= 0) {
if (maxSum < numbers[j].intValue()) {
maxSum = numbers[j].intValue();
left = j;
right = j;
}
if (++j >= numbers.length)
return;
}
i = ++j;
sum = 0;
}
j++;
}
System.out.println(String.format("Max subarray is %d, [%d; %d]", maxSum, left, right));
}
更新
代码的想法是只跟踪一个子数组,并添加到它的尾部数字,当数字太低以至于总和变为负数时 - 在尾部之后设置数组的开头。
此外,开头的负面项目将被忽略。子数组的头部只是向前移动。
每次总和似乎是最大值 - 更新 maxSum 和限制。
shift i() --to first non negative number
from j = i+1 up to N.length
sum + N[j]
if sum <= 0
i = j+1
if N[i] < 0
shift i()
sum = 0
我认为你的算法基本上是正确的,但它有两个我能看到的错误:
- 在输入
1 -2 10 3
上,它将跳过 10 并输出 3。我认为您可以通过将 i = ++j;
更改为 i = j;
来解决此问题。
- 在 2 个不同的地方你
return
如果 j
超过了结尾,这将导致根本没有输出! (例如,如果列表末尾出现一长串负数,就会发生这种情况。)
我也不认为它会比 Kadane 的更快(或更慢)。将两个数字相加是一项快速的操作,就像将一个变量复制到另一个变量一样快,这就是您在移动子数组的开头时所做的。
我正在读 Cormen 的 "Introduction to Algorithms"。
对于最大和子数组问题的线性算法,我提出了自己的解决方案。在实施之前没有检查现有的(Kadena 的)。
现在我正在用不同的测试场景对其进行测试,结果总是比嘉手纳的好。我不相信这样的运气,但找不到我错过的东西。你能看看它是否是一个可行的解决方案吗?
public void findMaxSubarray(Number[] numbers) {
int maxSum = Integer.MIN_VALUE;
int left = 0;
int right = numbers.length - 1;
int i = 0;
int j = i + 1;
int sum = numbers[i].intValue();
while (i < numbers.length) {
if (maxSum < sum) {
maxSum = sum;
left = i;
right = j - 1;
}
if (j >= numbers.length)
return;
sum = sum + numbers[j].intValue();
if (sum <= 0) {
// ignoring "first" negative numbers. shift i to first non-negative
while (numbers[j].intValue() <= 0) {
if (maxSum < numbers[j].intValue()) {
maxSum = numbers[j].intValue();
left = j;
right = j;
}
if (++j >= numbers.length)
return;
}
i = ++j;
sum = 0;
}
j++;
}
System.out.println(String.format("Max subarray is %d, [%d; %d]", maxSum, left, right));
}
更新 代码的想法是只跟踪一个子数组,并添加到它的尾部数字,当数字太低以至于总和变为负数时 - 在尾部之后设置数组的开头。 此外,开头的负面项目将被忽略。子数组的头部只是向前移动。 每次总和似乎是最大值 - 更新 maxSum 和限制。
shift i() --to first non negative number
from j = i+1 up to N.length
sum + N[j]
if sum <= 0
i = j+1
if N[i] < 0
shift i()
sum = 0
我认为你的算法基本上是正确的,但它有两个我能看到的错误:
- 在输入
1 -2 10 3
上,它将跳过 10 并输出 3。我认为您可以通过将i = ++j;
更改为i = j;
来解决此问题。 - 在 2 个不同的地方你
return
如果j
超过了结尾,这将导致根本没有输出! (例如,如果列表末尾出现一长串负数,就会发生这种情况。)
我也不认为它会比 Kadane 的更快(或更慢)。将两个数字相加是一项快速的操作,就像将一个变量复制到另一个变量一样快,这就是您在移动子数组的开头时所做的。