lis

For subtask $1$, let $D_i$ be the length of a longest increasing subsequence ending at position $i$. Check every $j<i$ with $A_j<A_i$ and add $1$ to the largest such $D_j$. If no such $j$ exists, set $D_i=1$. Store the preceding index as well to reconstruct a sequence. This takes $O(N^2)$ time.

For the full problem, maintain the smallest possible final value of an increasing subsequence for each length. When processing $A_i$, find the first stored value at least $A_i$ by binary search and update it. Equal values cannot extend a strictly increasing subsequence, so the search must find the first value greater than or equal to $A_i$, not the first strictly greater value.

Along with each final value, store the index of the element that produced it. When $A_i$ updates the state for length $k$, record the final index for length $k-1$ as its predecessor. Follow these predecessor indices from the final index of the longest length, then reverse the collected elements.

The time complexity is $O(N\log N)$ and the space complexity is $O(N)$ per case.

Solution written by GPT6