Ph.D. Qual Study Assistant

Longest Non-Decreasing Subsequence

1. The Problem

Given an array `A` of `n` integers, find the length of the longest subsequence where the elements are in non-decreasing order. A subsequence is derived from the original array by deleting zero or more elements without changing the order of the remaining elements.

Example: For `A = [9, 1, 8, 2, 7, 2, 1, 4]`, the longest non-decreasing subsequence is `[1, 2, 2, 4]`, and its length is 4.

2. The Idea: Dynamic Programming

We can solve this problem using dynamic programming. The core idea is to build the solution incrementally by answering the question: "What is the length of the longest non-decreasing subsequence that ends at index `i`?"

Let `dp[i]` be the length of the longest non-decreasing subsequence ending with the element `A[i]`. To compute `dp[i]`, we look at all previous elements `A[j]` where `j < i`. If `A[j] <= A[i]`, it means we can potentially extend a subsequence ending at `j` with the element `A[i]`. We want to find the longest such prior subsequence.

This gives us the recurrence relation:

dp[i] = 1 + max({dp[j] | 0 ≤ j < i and A[j] ≤ A[i]})

(If no such `j` exists, `dp[i] = 1`, as `A[i]` itself forms a subsequence of length 1).

The final answer is the maximum value in the entire `dp` array, as the longest subsequence could end at any index.

3. The Algorithm

  1. Create a DP array, `dp`, of size `n`.
  2. Initialize all elements of `dp` to 1 (since each element is a subsequence of length 1).
  3. Iterate with `i` from 1 to `n-1`:
    • Iterate with `j` from 0 to `i-1`:
      • If `A[j] <= A[i]`, it's a potential predecessor.
      • Update `dp[i] = max(dp[i], 1 + dp[j])`.
  4. Find the maximum value in the `dp` array. This is the length of the longest non-decreasing subsequence.

4. Complexity Analysis

Time Complexity: O(n²)
The algorithm consists of two nested loops. The outer loop runs `n-1` times (from `i = 1 to n-1`), and the inner loop runs `i` times (from `j = 0 to i-1`). This results in a total number of operations proportional to the sum 1 + 2 + ... + (n-1), which is O(n²).
Space Complexity: O(n)
We use an auxiliary array, `dp`, of size `n` to store the intermediate results. This requires O(n) additional space.

Algorithm Visualization