Longest Increasing Subsequence Problem Statement

Given 'N' students standing in a row with specific heights, your task is to find the length of the longest strictly increasing subsequence of their heights, ensuring the relative order remains unchanged.

Explanation:

A subsequence is a sequence derived from another sequence by deleting zero or more elements without changing the order of the remaining elements.

Input:

The first line of input contains an integer ‘T’ denoting the number of test cases. The first line of each test case contains an integer ‘N’ , the number of students in the row. The second line of each test case contains ‘N’ space separated integers representing the height of every student in the row.

Output:

For each test case, return the length of longest strictly increasing subsequence of heights.

Example:

Input:

T = 1 N = 5 heights = [10, 20, 10, 30, 40]

Output:

3

Explanation:

The longest increasing subsequence is [10, 30, 40] with length 3.

Constraints:

1

Question

Longest Increasing Subsequence Problem Statement

Given 'N' students standing in a row with specific heights, your task is to find the length of the longest strictly increasing subsequence of their heights, ensuring the relative order remains unchanged.

Explanation:

A subsequence is a sequence derived from another sequence by deleting zero or more elements without changing the order of the remaining elements.

Input:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains an integer ‘N’ , the number of students in the row.

The second line of each test case contains ‘N’ space separated integers representing the height of every student in the row.

Output:

For each test case, return the length of longest strictly increasing subsequence of heights.

Example:

Input:

T = 1
N = 5
heights = [10, 20, 10, 30, 40]

Output:

Explanation:

The longest increasing subsequence is [10, 30, 40] with length 3.

Constraints:

1 <= T <= 10
1 <= N <= 200
1 <= heights[i] <= 10^9
Time Limit: 1 sec

Accepted Answer

Find the length of the longest strictly increasing subsequence of heights of students in a row.

Iterate through the heights array and for each element, find the length of the longest increasing subsequence ending at that element.
Use dynamic programming to keep track of the longest increasing subsequence length for each element.
Return the maximum length found as the result.