What is the longest increasing subsequence problem and how is it solved?

Find the longest subsequence in an array where each element is strictly greater than the previous. The standard DP approach uses a one-dimensional table where dp at i represents the length of the longest increasing subsequence ending at index i. For each position, check all previous positions: if the element at j is smaller than at i, then dp at i equals the maximum of dp at i and dp at j plus one. This runs in O of n squared.