| Brute Force |
Generate all possible subsequences of the array (using recursion or bitmasking). For each subsequence, check if it is strictly increasing by comparing each pair of adjacent elements. Track and return the maximum length among all valid increasing subsequences. |
\(O(2^n \cdot n)\) There are \(2^n\) possible subsequences for an array of length \(n\). For each subsequence, checking if it is increasing takes up to \(O(n)\) time. So, total time is \(O(2^n \cdot n)\). |
\(O(n)\) The recursion stack or temporary storage for a subsequence can take up to \(O(n)\) space. |
| DP (Bottom-Up) |
Use a DP array where each entry \(dp[i]\) stores the length of the longest increasing subsequence starting at index \(i\). Iterate backwards, and for each \(i\), check all \(j > i\); if \(nums[j] > nums[i]\), update \(dp[i]\). The answer is the maximum value in \(dp\). |
\(O(n^2)\) For each index, we may check all following indices, leading to \(O(n^2)\) total operations. |
\(O(n)\) The DP array uses \(O(n)\) space. |