Maximum Box Stacking

You are given n boxes, where each box has a specified height. The goal is to stack as many boxes as possible such that each box placed on top of another is strictly taller than the box below it. This is equivalent to finding the length of the longest increasing subsequence (LIS) of the given heights. Formally, given a sequence of heights \(h_1, h_2, \dots, h_n\), find the maximum \(k\) such that there exists indices \(1 \leq i_1 < i_2 < \dots < i_k \leq n\) with \(h_{i_1} < h_{i_2} < \dots < h_{i_k}\).

The provided sample solution uses dynamic programming with an \(O(n^2)\) time complexity approach and works well for the problem sizes considered here.

inputFormat

The first line contains an integer (n) (the number of boxes, where (0 \leq n)). The second line contains (n) space-separated integers representing the heights of the boxes.

outputFormat

Output a single integer representing the maximum number of boxes that can be stacked such that each succeeding box is taller than the previous one.## sample

5
1 2 3 4 5

5