Longest Decreasing Subsequence - C++ Solution

1. Introduction

This blog post explores the problem of finding the length of the longest decreasing subsequence (LDS) in a given sequence. The LDS is a subsequence where the elements are in descending order and as long as possible.

Problem

Given a sequence of numbers, the task is to find the length of the longest subsequence where the elements are sorted in decreasing order.

Example:

Input: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

Output: 6

Explanation: A possible longest decreasing subsequence is [12, 10, 9, 5, 3].

2. Solution Steps

1. Use dynamic programming to build an array where each element represents the length of the longest decreasing subsequence ending with that element.

2. Initialize the array with 1 since the minimum length of LDS at each element is 1.

3. Iterate through the array and for each element, find the length of the longest LDS that can be formed.

4. Update the dynamic programming array based on the longest LDS found.

5. The maximum value in this array is the length of the longest LDS.

3. Code Program

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int longestDecreasingSubsequence(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    int maxLength = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLength = max(maxLength, dp[i]);
    }

    return maxLength;
}

int main() {
    vector<int> nums = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
    cout << "Length of longest decreasing subsequence: " << longestDecreasingSubsequence(nums) << endl;
    return 0;
}

Output:

Length of longest decreasing subsequence: 6

Explanation:

The longestDecreasingSubsequence function calculates the length of the longest decreasing subsequence in the given array. It uses dynamic programming to keep track of the length of the longest LDS ending at each element. By iterating over the array and comparing each element with its predecessors, the function updates the LDS lengths. The maximum value in the dynamic programming array represents the length of the longest LDS in the sequence, which is 6 for the given example.