“This is the 9th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Longest ascending subsequence

Today we’re going to look at a leetcode problem, the longest ascending subsequence

The title

Given an integer array nums, find the length of the longest strictly increasing subsequence.

A subsequence is a sequence derived from an array that deletes (or does not delete) the elements of the array without changing the order of the rest of the elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Answer:

This problem is not easy to solve using general methods, so here we use dynamic programming to solve this problem.

We first allocate an array dp and define dp[I] as nums, the longest sequence length ending in numS [I].

So how do we figure out dp[I]?

  1. Let’s define 0 <= j < I,
  2. When nums[I] > NUMs [j], it indicates that NUMs [I] is the increasing number of NUMs [j], and the longest ascending subsequence length is dp[j] +1.
  3. When nums[I] <=nums[j], the condition for ascending sequence is not met, and the sequence is skipped.
  4. Iterate over j, loop for steps 2 and 3. Count dp[I] = math.max (dp[I], dp[j] + 1);
  5. I is iterated until the entire NUMs is iterated. Calculate the largest value in dp[I], which is the answer.

Code implementation

function lengthOfLIS(nums) {
	if(nums.length === 0) return 0;
	const dp = new Array(nums.length).fill(1);
	let max = 1;
	for (let i = 0; i < nums.length; i++) {
		for (let j = 0; j < i; j++) {
			if(nums[i]>nums[j]) {
				dp[i] = Math.max(dp[i], dp[j] +1);
			}
			max = Math.max(max, dp[i]); }}return max;
}

console.log(lengthOfLIS([10.9.2.5.3.7.101.18]))
Copy the code

Ok, that’s all for today. In this code implementation, the total time is O(n^2), can you optimize the code to reduce the time to O(nlogn)?