How do you find Longest Increasing Subsequence (LIS)?

Short answer: Classic DP is O(n²): dp[i] = best LIS ending at i. The optimized patience-sorting / binary-search approach maintains tails of increasing subsequences in O(n log n). Mention both; implement O(n²) unless asked for optimal.

Complexity

DP O(n²); patience sorting O(n log n).

Common follow-ups

• Print one LIS
• Longest decreasing / bitonic subsequence

Interviewers love hearing both complexities even if you code the simpler DP.