Implement the longestIncreasingSubsequenceLength method that returns the length of the longest strictly increasing subsequence.
The input contains an integer array nums and its length size. Your task is to find the length of the longest increasing subsequence.
A subsequence is created by taking elements in the same order, but not necessarily from consecutive positions. The selected values must be strictly increasing. For example, in [10,9,2,5,3,7,101,18], one valid longest increasing subsequence is [2,3,7,101], so the answer is 4.
Example 1
[10,9,2,5,3,7,101,18]84Example 2
[0,1,0,3,2,3]64Example 3
[7,7,7]31Use dynamic programming where dp[i] means the length of the longest increasing subsequence ending at index i.
Every element alone has length 1. For each index i, check all previous indexes j. If nums[j] is smaller than nums[i], then nums[i] can extend the subsequence ending at j.
The answer is the maximum value stored in the dp array.
Pseudocode:
function longestIncreasingSubsequenceLength(nums, size):
if size == 0:
return 0
dp = array of size values filled with 1
answer = 1
for i from 0 to size - 1:
for j from 0 to i - 1:
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
answer = max(answer, dp[i])
return answer