LeetCode 300 Longest Increasing Subsequence - Why Naive Fails

Generate all subsequences and check which increasing ones are longest.

An array of length $n$ has $2^n$ subsequences. Checking each for increasing order is $O(n)$.

Total: $O(n \cdot 2^n)$. Far too slow.