Javascript Coding Test Course, Finding the Longest Increasing Subsequence

Problem Description

The problem of finding the Longest Increasing Subsequence (LIS) involves finding the longest subsequence within a given sequence while maintaining the order of increasing values. A subsequence does not need to be contiguous, but the chosen numbers must follow an increasing order.

Input Format

• The first line contains an integer N (1 ≤ N ≤ 1,000), which represents the length of the sequence.
• The second line contains N integers A1, A2, …, AN (1 ≤ Ai ≤ 1,000,000).

Output Format

Output the length of the longest increasing subsequence.

Example

Input Example

6
10 20 10 30 20 50

Output Example

4

Problem Solving Process

Step 1: Understand the Problem

To understand the problem, let’s examine the sequence. For the given sequence [10, 20, 10, 30, 20, 50], there are several possible increasing subsequences. Among them, the longest increasing subsequence is [10, 20, 30, 50], which has a length of 4. Therefore, the answer is 4.

Step 2: Choose an Algorithm

There are various algorithms for finding the longest increasing subsequence, but the most efficient method is to use dynamic programming. This method has a time complexity of O(N^2). I will use this method to solve the problem.

Step 3: Dynamic Programming Solution

function LIS(array) {
        const N = array.length;
        const dp = new Array(N).fill(1); // Initialize subsequence lengths to 1

        for (let i = 1; i < N; i++) {
            for (let j = 0; j < i; j++) {
                if (array[i] > array[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        return Math.max(...dp);
    }

    const sequence = [10, 20, 10, 30, 20, 50];
    console.log(LIS(sequence)); // Output: 4
    

Explanation

1. Declare the dp array to store the length of the longest increasing subsequence for each index. The initial value is set to 1 since each element can form a subsequence by itself.

2. Use two loops to compare indices i and j. If array[i] is greater than array[j], the value of dp[i] is updated to the maximum of dp[j] + 1 and the current value of dp[i]. This considers the subsequence that includes array[j] as well as array[i].

3. After all iterations, the largest value in the dp array will be the length of the longest increasing subsequence.

Result

Executing the above code will successfully determine the length of the longest increasing subsequence in the given sequence.

Conclusion

The Longest Increasing Subsequence (LIS) problem is one of the frequently asked algorithm problems. Through this problem, one can learn the basics of dynamic programming and enhance problem-solving skills in real coding tests. It is important to gain experience by solving various problems.