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

Question

In Code challange I have been asked a question. Questions asks me to return the length of the longest subsequence where sum of the difference between neighbours in the sorted(non-decreasing) subsequence is even. For every subsequence program should find the sorted(non-decreasing) version of the subsequence then should sum the difference between neighbours and check if it is even or not. For example, for the given array: [7,1,3,4,6,2,4] -> the subsequence should be whole array [7,1,3,4,6,2,4] -> because when it is sorted difference is even [1,2,3,4,4,6,7] -> 1+1+1+0+2+1 = 6(even), therefore, program should return 7. If the given array would be [7,3,4,6,2,4] then the program should return 5.

I feel like I should approach the question with dynamic programing, however, I am confused about how to handle the sorted constraint. What would be the most efficient approach to this question?

Answer 1

Observe that sum of the differences between adjacent elements is equal to the difference between minimum and maximum element. For example:

[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

So the question reduces to: Return the maximum length of the subsequence in which the difference between maximum and minimum element is even.

Naive Approach

First sort the array. Time complexity of sorting operation should be O(n log(n)) with a built-in sort function. Then find indices of:

1. first even element from left
2. first odd element from left
3. first even element from right
4. first odd element from right

Answer should be maximum of (index of 4 - index of 2 + 1, index of 3 - index of 1 + 1). You can find the indices in O(n) by two independent iteration over the array. You can find the implementation below.

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;
}

Output for [7,1,3,4,6,2,4]:

7

Output for [7,3,4,6,2,4]:

5

Overall time complexity = O(n log(n))

Better Approach

Notice that we do not need to sort the vector. Because what we have to do is to find number of elements between minimum even and maximum even, OR number of elements between minimum odd and maximum odd. We can solve the problem in O(n) without sorting the array. Implementation can be found below:

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;
}

Overall time complexity: O(n).