Longest Increasing Subsequence

[jsartisan]

Info

difficulty: medium
title: Longest Increasing Subsequence
type: question
template: typescript
tags: javascript, blind75, dynamic-programming, array

Question

Given an integer array nums, find the length of the longest strictly increasing subsequence.

Rules:

• Subsequence can skip elements (doesn't need to be contiguous)
• Must be strictly increasing (each number must be larger than previous)
• Elements must maintain relative order from original array

Constraints:

• 1 ≤ nums.length ≤ 1000
• -1000 ≤ nums[i] ≤ 1000

Examples:

// Example 1:
console.log(lengthOfLIS([9,1,4,2,3,3,7]));
// Output: 4
// Explanation: [1,2,3,7] is longest increasing subsequence

// Example 2:
console.log(lengthOfLIS([0,3,1,3,2,3]));
// Output: 4
// Explanation: [0,1,2,3] is one possible answer

Template

index.ts

export function lengthOfLIS(nums: number[]): number {

}

index.test.ts

import { lengthOfLIS } from './index';

describe('lengthOfLIS', () => {
  test('Example 1: Mixed sequence', () => {
    expect(lengthOfLIS([9,1,4,2,3,3,7])).toBe(4);
  });

  test('Example 2: Multiple valid solutions', () => {
    expect(lengthOfLIS([0,3,1,3,2,3])).toBe(4);
  });

  test('Single element', () => {
    expect(lengthOfLIS([5])).toBe(1);
  });

  test('Already sorted', () => {
    expect(lengthOfLIS([1,2,3,4,5])).toBe(5);
  });

  test('Decreasing sequence', () => {
    expect(lengthOfLIS([5,4,3,2,1])).toBe(1);
  });

  test('All same numbers', () => {
    expect(lengthOfLIS([1,1,1,1])).toBe(1);
  });

  test('Two increasing numbers', () => {
    expect(lengthOfLIS([1,2])).toBe(2);
  });

  test('Complex sequence', () => {
    expect(lengthOfLIS([3,10,2,1,20])).toBe(3);
  });

  test('Sequence with negatives', () => {
    expect(lengthOfLIS([-2,-1,0,1])).toBe(4);
  });

  test('Long sequence', () => {
    expect(lengthOfLIS([1,3,6,7,9,4,10,5,6])).toBe(6);
  });
});

[github-actions[bot]]

302 - Pull Request updated.