The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

A Subsequence

A subsequence is a sequence that can be derived from an array or another sequence, by removing zero or more elements, without changing the order of the remaining elements. The subsequence maintains the order it had in the original array or original sequence.

In general, for the original sequence of size n, there can be up to (2ⁿ - 1) non-empty sub-sequences in total.

For example, in the array [1, 2, 3, 4], there are 15 non-empty sub-sequences, which are:

[1], [2], [3], [4], [1,2], [1,3],[1,4], [2,3], [2,4], [3,4], [1,2,3], [1,2,4], [1,3,4], [2,3,4], [1,2,3,4] .

This is the number of combinations, but maintaining the order of appearance in the given (original) array.

A complete (power set) of subsequences of any array includes the empty subsequence: []. With that, the total number of possible subsequences from the original array is 2ⁿ .

Even-number only type subsequences from the 15 subsequences above, are:

[2], [4], [2,4]

which are not up to half of the 15 subsequences constituting the whole set (of subsequences).

Odd-number only type subsequences from the 15 subsequences above, are:

[1], [3], [1,3]

which are not up to half of the 15 subsequences constituting the whole set (of subsequences).

Out of the whole set of possible subsequences, only one or more subsequences with a characteristic description, is usually required.

Two Pointers Technique

Two pointers refer to left (i) and right (j) indexes, such that left points to the start of the array and right points to the end of the array, initially. The opposite pointers move towards the center of the array during iterations, until a condition is met.

A Sliding Window

A sliding window is a sub-array that moves from one end of the array to the other end, one element at a time. The left end of the window is typically identified by the variable, i or left or back. The right end of the window is typically identified by the variable, j or right or front.

As the window moves, its size (length) may be fixed or variable.

The sliding window is a specialized application of the two-pointers technique.

Problem

Given an array A[] containing N integers, the task is to print the length of the longest subsequence of even numbers in the array.

Examples:

Input: A[] = {3, 4, 11, 2, 9, 21}
Output: 2
Explanation:
The longest subsequence containing even numbers is {4, 2}.
Hence, the answer is 2.

Input: A[] = {6, 4, 10, 13, 9, 25}
Output: 3
The longest subsequence containing even numbers is {6, 4, 10}.
Hence, the answer is 3.

Strategy

Just scan the given array once. While scanning, be counting the even numbers.

To know if a number is even, divide the number by 2 and if the remainder is 0, it means the number is even. If the remainder is 1, it means the number is odd. Use modulus division. Thus:

    remainder = number % 2

Program in O(n) Time

The smart program is (read through the code and comments):

#include <stdio.h>

int longestEvenSubsequenceLength(int A[], int n) {
    int counter = 0;

    for (int i = 0; i < n; i++) {
        if (A[i] % 2 == 0)
            counter = counter + 1;
    }
        
    return counter;
}

int main(int argc, char **argv) {
    int A[] = {6, 4, 10, 13, 9, 25};
    int n = sizeof(A) / sizeof(A[0]);
    int ret = longestEvenSubsequenceLength(A, n);
    printf("%i\n", ret);
    
    return 0;
}

The output is:

    3

The time complexity is O(n), where n is the length of the array. The space complexity is O(n), where n is the length of the same array in the calling function and called function. Any extra time or extra space used is ignored, in quoting the time or space complexity.

A very similar algorithm can be used to determine the sum of the longest even number subsequence, or print the sum of the longest even number sequence.

Still, a very similar algorithm can be used to determine the length of the longest negative even number subsequence, or the sum of the longest negative even number subsequence, or print the longest negative even number subsequence.

It can similarly be done for odd numbers.

Thanks for reading.