最长子序列的长度，相邻子序列之间的差和为偶数

Question

在代码挑战中，有人问我一个问题。问题要求我返回最长子序列的长度，其中排序(非递减(子序列中相邻子序列之间的差之和为偶数。对于每个子序列，程序应该找到子序列的排序(非递减(版本，然后对邻居之间的差异求和，并检查其是否偶数。例如，对于给定的数组：[7,1,3,4,6,2,4]->子序列应该是整个数组[7，1，3，4，6，2，4]->因为当它被排序时，差异是偶数[1,2,3,4,4,6,7]->1+1+1+0+2+1=6(偶数(，因此，程序应返回7。如果给定的数组是[7，3，4，6，2，4]，那么程序应该返回5。

我觉得我应该用动态编程来处理这个问题，然而，我对如何处理排序约束感到困惑。解决这个问题最有效的方法是什么？

Answer 1

观察相邻元素之间的差值之和等于最小元素和最大元素之间的差。例如：

[x1, x2, x3, x4] = [x1, x1 + a, (x1 + a) + b, ((x1 + a) + b) + c, (((x1 + a) + b) + c) + d]
Sum of differences = a + b + c + d = x4 - x1

因此，问题简化为：返回子序列的最大长度，其中最大元素和最小元素之间的差是偶数。

天真的方法

首先对数组进行排序。排序操作的时间复杂度应为O(n log(n))，并内置排序函数。然后查找以下索引：

1. 左起第一个偶数元素
2. 左起第一个奇数元素
3. 右起第一个偶数元素
4. 右起第一个奇数元素

答案的最大值应为(4的索引-2+1的索引，3的索引-1+1的索引(。您可以通过在数组上进行两次独立的迭代来找到O(n)中的索引。您可以在下面找到实现。

int main() {
vector<int> vec = {7,3,4,6,2,4};
sort(vec.begin(), vec.end());
int firstOddLeft = -1;
int firstEvenLeft = -1;
for(int i=0; i<vec.size(); i++) {
if(firstOddLeft != -1 && firstEvenLeft != -1) break;
if(vec[i] % 2 == 0 && firstEvenLeft == -1) firstEvenLeft = i;
if(vec[i] % 2 != 0 && firstOddLeft == -1) firstOddLeft = i;
}

int firstOddRight = -1;
int firstEvenRight = -1;
for(int i=vec.size()-1; i>=0; i--) {
if(firstOddRight != -1 && firstEvenRight != -1) break;
if(vec[i] % 2 == 0 && firstEvenRight == -1) firstEvenRight = i;
if(vec[i] % 2 != 0 && firstOddRight == -1) firstOddRight = i;
}
int subsequenceLength = 0;
if(firstEvenLeft != -1 && firstOddLeft != -1) subsequenceLength = max(firstEvenRight - firstEvenLeft + 1, firstOddRight - firstOddLeft + 1);
else if(firstEvenLeft != -1) subsequenceLength = firstEvenRight - firstEvenLeft + 1;
else if(firstOddLeft != -1) subsequenceLength = firstOddRight - firstOddLeft + 1;
else subsequenceLength = -1;
if(subsequenceLength == -1) cout << "No such subsequence" << endl;
else cout << subsequenceLength << endl;
return 0;
}

[7,1,3,4,6,2,4]:的输出

7

[7,3,4,6,2,4]:的输出

5

总体时间复杂性=O(n log(n))

更好的方法

请注意，我们不需要对向量进行排序。因为我们要做的是找到最小偶数和最大偶数之间的元素数量，或者最小奇数和最大奇数之间的元素数。我们可以在不排序数组的情况下解决O(n)中的问题。实现方式如下：

int main() {
vector<int> vec = {7,1,3,4,6,2,4};
// find minimum even number: mine
// find maximum even number: maxe
// find minimum odd number: mino
// find maximum odd number: maxo
int mine = INT_MAX, mino = INT_MAX;
int maxe = INT_MIN, maxo = INT_MIN;
for(auto& c: vec) {
if(c % 2) {
mino = min(mino, c);
maxo = max(maxo, c);
} else {
mine = min(mine, c);
maxe = max(maxe, c);
}
}
int cntE = 0;
int cntO = 0;
for(auto& c:vec) {
if(c >= mine && c <= maxe) cntE++;
if(c >= mino && c <= maxo) cntO++;
}
cout << max(cntE, cntO)<< endl;
return 0;
}

总体时间复杂度：O(n)。