HEIGHTIQP- Editorial

editorial
, ,
1

Problem Link - Students, heights and their IQs

Problem Statement:

In the school morning assembly, there are n students standing in a line, each with a height and IQ level. The task is to find the longest subsequence of students with strictly increasing heights and strictly decreasing IQ levels. A subsequence can be formed by removing some (or no) students.

Approach:

The solution uses dynamic programming to find the longest valid subsequence. We maintain an array DP where DP[i] represents the length of the longest subsequence ending at student i.

  1. Dynamic Programming Initialization: Initialize the DP array with all values set to 1, indicating each student can be a subsequence by themselves.
  2. Building the DP Array: For each student i, check previous students j:

    • Skip if H[j] >= H[i] (not strictly increasing) or IQ[j] <= IQ[i] (not strictly decreasing).

    • Update DP[i] to be the maximum of its current value or 1 + DP[j] if both conditions are satisfied.

  3. Finding the Maximum Length: After populating the DP array, find the maximum value, representing the longest valid subsequence.

This method efficiently calculates the longest subsequence using relationships between students based on their heights and IQ levels.

Time Complexity:

  • O(n²) for each test case, where n is the number of students.

Space Complexity:

  • O(n) due to the DP array used to store subsequence lengths.