计算与偶数之和的数组中数字的最大数量。
我有这段代码，据我所知，它在给定数组中搜索最大的连续数字数量，该数组和是偶数。
private static int f (int[]a, int low, int high)
{
int res = 0;
for (int i=low; i<=high; i++)
res += a[i];
return res;
}
public static int what (int []a)
{
int temp = 0;
for (int i=0; i<a.length; i++)
{
for (int j=i; j<a.length; j++)
{
int c = f(a, i, j);
if (c%2 == 0)
{
if (j-i+1 > temp)
temp = j-i+1;
}
}
}
return temp;
} 例如，数组-3,4,8，-1,15应该返回"4“作为和回答，因为-3+4+8-1 = 8，而8是偶数。
我需要一个如何使它更有效率的想法(+现在它的效率是什么？)O(n^3)？)
提前谢谢。
回答 1
Stack Overflow用户
发布于 2015-06-08 10:09:25
您只需要一个循环，这将采取O(n)。
您需要对数组进行一次迭代，并计算偶数数和奇数数。如果evenCount + oddCount为偶数，则输出为evenCount + oddCount - 1，否则为evenCount + oddCount - 1。
原因是所有偶数之和都是偶数。每个奇数对的和也是偶数，所以大多数元素的偶数和都有一些元素，它们要么是数组的长度(如果有偶数奇数)，要么是数组的长度-1(如果有奇数奇数，则必须从和中排除其中一个元素才能得到偶数和)。
实际上，你只需数一下奇数：
public static int maxEvenSumLength (int []a)
{
int oddCount = 0;
for (int i=0; i<a.length; i++)
{
if (a[i] % 2 == 1) {
oddCount++;
}
}
return (oddCount % 2 == 0) ? a.length : (a.length - 1);
} 编辑：
我忽略了一个事实，即具有偶数和的元素应该是连续的。在这种情况下，如果奇数的数目是偶数，则结果仍然是数组的长度。区别在于奇数的数目是奇数。在这种情况下，您应该找到最接近数组两端的奇数，并且连续偶数和的长度将是最后一个奇数之前或第一个奇数之后的元素数(两者中较大的)。
public static int maxConsecutiveEvenSumLength (int []a)
{
int oddCount = 0;
int firstOddIndex = -1;
int lastOddIndex = a.length;
for (int i=0; i<a.length; i++)
{
if (a[i] % 2 == 1) {
oddCount++;
if (firstOddIndex < 0)
firstOddIndex = i;
lastOddIndex = i;
}
}
if (oddCount % 2 == 0) {
return a.length;
} else {
return Math.max(a.length - firstOddIndex - 1,lastOddIndex);
}
} 我们仍然对数组进行一次迭代，因此时间复杂度仍然是O(n)。
https://stackoverflow.com/questions/30706324
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号