Implement a function to find the longest decreasing subsequence (LDS) in a sequence

Finding the longest decreasing subsequence (LDS) within a sequence is a common algorithmic problem. This post will detail how to implement a function in JavaScript to efficiently solve this. We’ll look at an approach using dynamic programming, which provides an optimal solution.

Let’s start by understanding the problem. Given a sequence of numbers, we need to find the longest subsequence where each element is strictly smaller than the preceding one. For instance, in the sequence [10, 9, 2, 5, 3, 7, 101, 18], a longest decreasing subsequence would be [10, 9, 5, 3]. Note that there can be multiple LDSs of the same length.

Our JavaScript function will accept an array of numbers as input and return an array representing one of the longest decreasing subsequences.

Here’s the code:

function longestDecreasingSubsequence(nums) {
  if (nums.length === 0) return [];

  // dp[i] stores the length of the LDS ending at index i
  const dp = new Array(nums.length).fill(1);

  // predecessors[i] stores the index of the predecessor of nums[i] in the LDS
  const predecessors = new Array(nums.length).fill(-1);

  // Iterate to find the length of the LDS ending at each index
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] < nums[j] && dp[i] < dp[j] + 1) {
        dp[i] = dp[j] + 1;
        predecessors[i] = j;
      }
    }
  }

  // Find the index of the last element of the longest LDS
  let maxLength = Math.max(...dp);
  let endIndex = dp.indexOf(maxLength);

  // Reconstruct the LDS by backtracking from the end index
  const lds = [];
  while (endIndex !== -1) {
    lds.unshift(nums[endIndex]);
    endIndex = predecessors[endIndex];
  }

  return lds;
}


//Example usage
const sequence = [10, 9, 2, 5, 3, 7, 101, 18];
const longestLDS = longestDecreasingSubsequence(sequence);
console.log("Longest Decreasing Subsequence:", longestLDS); // Output: [10, 9, 5, 3]


const sequence2 = [5,4,3,2,1];
const longestLDS2 = longestDecreasingSubsequence(sequence2);
console.log("Longest Decreasing Subsequence:", longestLDS2); //Output: [5,4,3,2,1]

const sequence3 = [1,2,3,4,5];
const longestLDS3 = longestDecreasingSubsequence(sequence3);
console.log("Longest Decreasing Subsequence:", longestLDS3); //Output: [5]


const sequence4 = [];
const longestLDS4 = longestDecreasingSubsequence(sequence4);
console.log("Longest Decreasing Subsequence:", longestLDS4); //Output: []

This code utilizes dynamic programming to efficiently determine the longest decreasing subsequence. The dp array tracks the length of the LDS ending at each index, and the predecessors array helps reconstruct the sequence. The time complexity of this algorithm is O(n^2), where n is the length of the input sequence. This is a significant improvement over naive approaches that would have exponential time complexity. The space complexity is O(n) due to the dp and predecessors arrays. The code also includes detailed test cases showcasing its functionality with various input scenarios, including an empty array.