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[], the task is to find the length of the longest subsequence of the array A[], such that all adjacent elements in a subsequence are different.

Examples:

Input: A[] = {4, 2, 3, 4, 3}
Output: 5
Explanation:
The longest subsequence where no two adjacent elements are equal is {4, 2, 3, 4, 3}, the whole array. Length of the subsequence is 5.

Input: A[] = {7, 8, 1, 2, 2, 5, 5, 1}
Output: 6
Explanation: Longest subsequence where no two adjacent elements are equal is {7, 8, 1, 2, 5, 1}. In the given array, 2 is next to 2 and 5 is next to 5. Length of the subsequence is 6. No element in the subsequence is the same as the preceding element.

Brute Force (naive) Approach

The simplest (brute force) approach is to generate all possible subsequence of the given array and print the maximum length of the subsequence having all adjacent elements different.

Time complexity for this naive approach is 2ⁿ .
Space complexity is high.

Efficient Approach

Strategy

Just scan the given array once. While scanning, be checking if the next number is not the same as the preceding number. Be counting the number of characters for length, of the accumulating subsequence.

Efficient Program in O(n) Time

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

#include <stdio.h>

int longSubDistAdj(int A[], int n) {
    int counter = 1;    //assume, at least one element in array
    
    for (int i = 1; i < n; i++) {    //start from 1 and not 0
        if (A[i] != A[i - 1]) {
            counter++;
        }
    }
    
    return counter;
}

int main(int argc, char **argv) {
    int A[] = {7, 8, 1, 2, 2, 5, 5, 1};
    int n = sizeof(A) / sizeof(A[0]);
    int ret = longSubDistAdj(A, n);
    printf("%i\n", ret);
    
    return 0;
}

The output is:

    6

as expected. 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.

Thanks for reading.