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

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)。