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

Question

在代码挑战中有人问我一个问题。问题问我 return 最长子序列的长度，其中排序（非递减）子序列中邻居之间的差之和是偶数。对于每个子序列程序应该找到子序列的排序（非递减）版本然后应该对邻居之间的差异求和并检查它是否均匀。例如，对于给定的数组： [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(even)，因此，程序应该 return 7. 如果给定的数组是 [ 7,3,4,6,2,4] 那么程序应该 return 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

所以问题简化为：Return最大和最小元素之差为偶数的子序列的最大长度

天真的方法

首先对数组进行排序。排序操作的时间复杂度应该是O(n log(n))，排序函数是built-in。然后找到索引：

左起第一个 even 个元素
左起第一个奇数个元素
第一个 even 个元素
第一个奇数个元素

答案应该是（索引 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).

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

length of the longest subsequence that difference between neighbors sums to an even number

algorithm

dynamic-programming

天真的方法

更好的方法