Array Dynamic Programming
Proficient Level

Implement the method longestIncreasingSubsequence that returns the length of the longest strictly increasing subsequence.

A subsequence keeps original order but may skip elements. The chosen values must be strictly increasing.

The task is designed to test careful handling of edge cases, not only the most common input.

  • Use only the first size elements.
  • Return the length, not the subsequence itself.
  • Equal values cannot extend a strictly increasing subsequence.
Example 1
Input:
nums (int[]) = [10,9,2,5,3,7,101,18]
size (int) = 8
Return:
(int) 4
Example 2
Input:
nums (int[]) = [0,1,0,3,2,3]
size (int) = 6
Return:
(int) 4
Example 3
Input:
nums (int[]) = [7,7,7,7]
size (int) = 4
Return:
(int) 1

Let dp[i] be the best subsequence length ending at index i, then extend from earlier smaller values.

Run your code to see the result.