LIS O(n²)

The direct DP formulation: dp[i] = length of the longest increasing subsequence ending at i.