Return the length of the longest strictly increasing subsequence of the array (a subsequence keeps order but may skip elements).
maxIncreasingSubseq(nums)
Input format: space-separated integers (may be empty → 0).
[10, 9, 2, 5, 3, 7, 101, 18] // → 4 (2, 3, 7, 101)
[0, 1, 0, 3, 2, 3] // → 4
[7, 7, 7] // → 1
A subsequence doesn't need to be contiguous — skip elements freely, preserving order. That freedom makes brute force expensive: 2ⁿ possible subsequences for a list of length n, since each element is independently included or excluded. Checking all directly is infeasible beyond tiny inputs.
Tame the exponential search by finding smaller subproblems the full problem decomposes into. Fix where an increasing subsequence ends — does that tell you something reusable?
Yes. Knowing the longest increasing subsequence ending at each index, the best one ending at a new index i is: look at every earlier index j with a smaller value (nums[i] could legally extend it), take the longest so far, add one. No smaller earlier value means starting fresh at length 1.
The best subsequence ending at i has some predecessor as its second-to-last element (or none), and the subsequence up to that predecessor must itself be optimal ending there — otherwise you could swap in a better one and get an even longer result at i, contradicting optimality. This optimal-substructure property justifies building the answer from smaller, already-solved pieces.
Process indices left to right. For each i, scan every earlier j: is nums[j] less than nums[i], and would extending it beat what's currently recorded for i? Keep the best. Track a running maximum across all indices, since the longest subsequence overall doesn't have to end at the last element.
Each of n indices scans up to n earlier ones — O(n²) time, O(n) space. A binary-search-based optimization tracking "smallest possible tail values per length" gets this to O(n log n), but the O(n²) DP is the right first approach — it directly mirrors the recursive reasoning above.
def max_increasing_subseq(nums):
if len(nums) == 0:
return 0
dp = [1] * len(nums)
best = 1
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
if dp[i] > best:
best = dp[i]
return best
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.