配对元素以获得最大数量的偶数和

Question

给定一个由 N 个整数组成的循环数组（即 A[0] 和 A[N - 1] 彼此相邻），相邻的最大数量是多少 您可以组成其总和为偶数的对？请注意，每个元素最多可以属于一对。

例如，如果我们有 [5, 7, 9, 6, 3]，那么您应该将 (5, 3) 和 (7, 9) 配对以获得 2 的答案。另外，如果我们有 [1, 1, 1, 1, 1, 1]，那么答案是 3（将每个相邻元素配对而不环绕）

这是我最近面试时遇到的一个问题，目前还解决不了（没有得到工作）。我知道具有相同奇偶校验的两个数字的总和会产生偶数和（奇数和奇数，或者偶数和偶数），但整个“环绕”部分才是让我着迷的地方。特别是，我无法确定将一个值与其左邻居或右邻居配对是否是最佳选择。目前我想到的算法如下：

• 对于每个索引 0 <= i <= n - 1, try to pair A[i] with A[i + 1] by checking their parity.

• 如果 A[0] 和 A[n-1] 最后都未配对，如果奇偶校验相同，则将它们配对。

这是一个错误的算法，因为它对于 [1, 1, 1, 0, 1] 失败，在这种情况下，最好将 A[0] 与 A[n-1] 配对，将 A[1] 与 A[2] 配对。有没有人有什么建议？我在想也许是动态规划的一些东西，但我不确定。圆形部分真让我失望。

谢谢。

Answer 1

如果所有数字都是奇数，或者所有数字都是偶数，那么

• 如果数组长度是偶数，则包含所有数字（无论如何分组）。
• 如果是奇数，则包括除最小的数字之外的所有数字。

如果同时存在奇数和偶数，则可以将数组分为奇数游和偶数游。如果第一次和最后一次都是偶数或都是奇数，则将它们连接起来。分别解决每次运行的问题。这很容易，因为运行不是圆形的。如果游程的长度是偶数，则包括所有数字。否则，排除 even 位置处的最小数字。

这假设所有数字都是非负数。

Answer 2

int solution(vector<int> A) {
    int n = A.size();
    
    int ans1 = 0, ans2 = 0;
    {
        vector<int> dp(n, 0);
        for(int i = 1;i<n;i++){
            if((A[i] + A[i-1]) % 2 == 0){
                dp[i] = max(dp[i], 1 + ((i-2>=0)?dp[i-2]:0));
            }
            ans1 = max(ans1, dp[i]);
        }
    }
    {
        A.push_back(A[0]);
        A.erase(A.begin());
        vector<int> dp(n, 0);
        for(int i = 1;i<n;i++){

            if((A[i] + A[i-1]) % 2 == 0){
                dp[i] = max(dp[i], 1 + ((i-2>=0)?dp[i-2]:0));
            }
            ans2 = max(ans2, dp[i]);
        }
    }

    return max(ans1, ans2);
}