Array Reflection Height Maximization — Problem Statement & Solution Guide
Problem Description
Given an array of integers reflections where each element represents a floor number visible from a bird's-eye view, determine the maximum possible height of the tower by finding the longest increasing subsequence in the reflections array.
Examples
Input
[1, 2, 3, 4, 5]
Output
5
Explanation: Step-by-step: Given the array [1, 2, 3, 4, 5], we can find the longest increasing subsequence by selecting the elements in order: [1, 2, 3, 4, 5]. The length of this subsequence is 5, which is the maximum possible height of the tower.
Input
[5, 4, 3, 2, 1]
Output
1
Explanation: Step-by-step: Given the array [5, 4, 3, 2, 1], we can find the longest increasing subsequence by selecting the elements in order: [1]. The length of this subsequence is 1, which is the maximum possible height of the tower.
Constraints
- 1 ≤ floorNumbers.length ≤ 10^5
- 1 ≤ floorNumbers[i] ≤ 10^6
- The floor numbers in the reflection list may or may not be present in their original order
Optimal Approach & Strategy
The optimal approach to solve this problem is to sort the floor numbers in descending order, and then construct all possible valid configurations starting from the maximum value.
Brute Force Approach
One possible approach to solve this problem is to use the brute force method, which involves iterating through all possible configurations of the tower and checking if it is valid.
Verified Code Solutions
function findMaxHeight(reflections) { let n = reflections.length; if (n === 0) return 0; let dp = new Array(n).fill(1); for (let i = 1; i < n; i++) { let max = 0; for (let j = 0; j < i; j++) { if (reflections[i] > reflections[j] && dp[j] + 1 > max) max = dp[j] + 1; } dp[i] = Math.max(max, dp[i]); } let max = 0; for (let i = 0; i < n; i++) { max = Math.max(max, dp[i]); } return max; }class Solution {
public int longestIncreasingSubsequence(int[] reflections) {
int n = reflections.length;
int[] dp = new int[n];
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (reflections[i] > reflections[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
}
}
}
return Arrays.stream(dp).max().getAsInt();
}
}def longest_increasing_subsequence(reflections):
n = len(reflections)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if reflections[i] > reflections[j] and dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
return max(dp)function findMaxHeight(reflections) { let n = reflections.length; if (n === 0) return 0; let dp = new Array(n).fill(1); for (let i = 1; i < n; i++) { let max = 0; for (let j = 0; j < i; j++) { if (reflections[i] > reflections[j] && dp[j] + 1 > max) max = dp[j] + 1; } dp[i] = Math.max(max, dp[i]); } let max = 0; for (let i = 0; i < n; i++) { max = Math.max(max, dp[i]); } return max; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.