查找最大和连续子数组-另一个版本

这个论坛上有很多关于寻找最大和连续子数组的帖子。然而，这个问题的一个小变化是，子阵列至少应该有两个元素。

例如，对于输入[-2, 3, 4, -5, 9, -13, 100, -101, 7]，下面的代码给出100。但是，有了上述限制，对于子阵列[3, 4, -5, 9 , -13, 100]，它将是98。有人能帮我做这个吗？我找不到合适的逻辑。

#include<stdio.h>
int maxSubArraySum(int a[], int size)
{
int max_so_far = 0, max_ending_here = 0;
int i;
for(i = 0; i < size; i++)
{
max_ending_here = max_ending_here + a[i];
if(max_ending_here < 0)
max_ending_here = 0;
if(max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
} 
/*Driver program to test maxSubArraySum*/
int main()
{
int a[] = {-2, 3, 4, -5, 9, -13, 100, -101, 7};
int n = sizeof(a)/sizeof(a[0]);
int max_sum = maxSubArraySum(a, n);
printf("Maximum contiguous sum is %dn", max_sum);
getchar();
return 0;
}

更新1:根据starrify进行了更改，但我没有得到我所期望的。它给出的是183而不是98。

#include<stdio.h>
const int size = 9;
int maxSubArraySum(int a[])
{
int max_so_far = 0;
int i;
int max_ending_here[size];
int sum_from_here[size];
max_ending_here[0] = a[0];
//sum_from_here[0] = a[0] + a[1];
for (i = 1; i < size; i++)
{
max_ending_here[i] = max_ending_here[i-1] + a[i];
sum_from_here[i] = a[i-1] + a[i];
if (max_so_far < (max_ending_here[i] + sum_from_here[i]))
max_so_far = max_ending_here[i] + sum_from_here[i];
}
return max_so_far;
}
/*Driver program to test maxSubArraySum*/
int main()
{
int a[] = { -2, 3, 4, -5, 9, -13, 100, -101, 7 };
int n = sizeof(a) / sizeof(a[0]);
int max_sum = maxSubArraySum(a);
printf("Maximum contiguous sum is %dn", max_sum);
getchar();
return 0;
}

方法：

设max_ending_here是一个数组，其元素max_ending_here[i]表示刚好在索引i之前(不包括)结束的子数组(可以是空的)的最大和。要计算它，请使用与函数maxSubArraySum中相同的方法。时间复杂度为O(n)，空间复杂度为O(n)。
设sum_from_here是一个数组，其元素sum_from_here[i]表示从(包括)索引i开始的长度为2的子数组的和，即sum_from_here[i] = a[i] + a[i + 1]。时间复杂度为O(n)，空间复杂度为O(n)。
遍历所有有效索引并找到max_ending_here[i] + sum_from_here[i]的最大值：该值就是您要查找的值。时间复杂度为O(n)，空间复杂度为O(1)。

因此总的时间复杂度为O(n)，空间复杂度为O(n)。

这种方法可以扩展到任意的最小长度——不仅是2；空间复杂性不会增长。

您在maxSubArraySum中的原始实现实际上是上述方法的一个特殊情况，其中最小子数组长度为0。

编辑：

根据您在更新1中提供的代码，我做了一些更改，并在此处提供了正确的版本：

int maxSubArraySum(int a[])
{
int max_so_far = 0;
int i;
int max_ending_here[size];
int sum_from_here[size];
max_ending_here[0] = 0;
for (i = 1; i < size - 1; i++)
{
max_ending_here[i] = max_ending_here[i - 1] + a[i - 1];
if (max_ending_here[i] < 0)
max_ending_here[i] = 0;
sum_from_here[i] = a[i] + a[i + 1];
if (max_so_far < (max_ending_here[i] + sum_from_here[i]))
max_so_far = max_ending_here[i] + sum_from_here[i];
}
return max_so_far;
}

请注意，密钥是max_ending_here[i]和sum_from_here[i]不应重叠。这里有一个例子：

-2   3   4   -5   9   -13   100   -101   7
| 3   4   -5   9 | -13   100 |
|              |
|              |
this            |
is             |
max_ending_here[5]    |
|
this
is
sum_from_here[5]

您可以使用我在这里实现的滑动窗口算法来解决这个问题。

在算法的所有阶段，我们都保持以下

一个窗口[lo…hi]
当前窗口的总和
一个名为index的变量，它跟踪当前窗口中的坏前缀，删除会增加总和的值。因此，如果我们去掉前缀[lo…index]，那么新窗口变成[index+1…hi]，并且随着[lo…index]的和为负，和增加
存储在变量prefixSum中的前缀的总和。它保持区间[lo…index]的和
迄今为止找到的最好的Sum

初始化

window=[0…1]
sum=arr[0]+arr1
索引=0
prefixSum=arr[0]

现在，在while循环的每次迭代中，

检查当前窗口中是否存在前缀，删除会增加总和的值
将列表中的下一个值添加到当前间隔，并更改窗口和总和变量
更新bestSum变量

下面的工作Java代码实现了上述解释。

int lo = 0;
int hi = 1;
int sum = arr[0] + arr[1];
int index = 0;
int prefixSum = arr[0];
int bestSum = sum;
int bestLo = 0;
int bestHi = 1;
while(true){
// Removes bad prefixes that sum to a negative value. 
while(true){
if(hi-index <= 1){
break;
}
if(prefixSum<0){
sum -= prefixSum;
lo = index+1;
index++;
prefixSum = arr[index];
break;
}else{
prefixSum += arr[++index];
}
}
// Update the bestSum, bestLo and bestHi variables. 
if(sum > bestSum){
bestSum = sum;
bestLo = lo;
bestHi = hi;
}
if(hi==arr.length-1){
break;
}
// Include arr[hi+1] in the current window. 
sum += arr[++hi];
}
System.out.println("ANS : " + bestSum);
System.out.println("Interval : " + bestLo + " to " + bestHi);

在算法lo+1<hi，在while循环的每一步，我们将hi加1。此外，变量lo和索引都不会减少。因此，时间复杂性在输入的大小上是线性的。

时间复杂度：O(n)
空间复杂度：O(1)

相关内容

最新更新

热门标签：