This problem mainly involves dynamic programming, optimization can consider greedy algorithm and binary search.

The original problem

Given an unordered array of integers, find the length of the longest ascending subsequence.

Example:

Input: [10,9,2,5,3,7,101,18] output: 4 explanation: the longest ascending subsequence is [2,3,7,101], which has a length of 4.Copy the code

Description:

  • There can be multiple combinations of the longest ascending subsequence, and you just output the corresponding length.
  • The time complexity of your algorithm should be O(n2).

Advanced: Can you reduce the time complexity of the algorithm to O(n log n)?

The problem solving

Violence law

And that’s the basic idea, using recursion, you start with each number, you look for it one by one, as long as it’s bigger than the one you picked, you start with the new number and you keep looking. Once you’re done, find the longest sequence.

Take a look at the code, too:

Class Solution {public int recursiveSearch(int[] nums) {return recursiveSearch(nums, integer.min_value, 0); } public int recursiveSearch(int[] nums, int standard, int index) { if (nums.length == index) { return 0; } // If it contains the current index number, its increment length int tokenLength = 0; if (nums[index] > standard) { tokenLength = 1 + recursiveSearch(nums, nums[index], index + 1); Int notTokenLength = recursiveSearch(nums, standard, index + 1); TokenLength > notTokenLength? tokenLength : notTokenLength; }}Copy the code

After submission, the report exceeds the time limit, which is expected, so let’s optimize it.

Recording intermediate results

To analyze the violence solution, assume that nums is: [10,9,2,5,3,7,101,18], then the lookup from 7 to 101 has been searched at 2,5, and 3.

So in this case of repeated search, we can use a two-dimensional array to record the intermediate results, so as to achieve optimization effect. For example, if int[][] result is marked as an array of intermediate results, result[I][j] represents the maximum increasing sequence length from nums[i-1] with or without NUMs [j]. This will ensure that there is no double counting.

Let’s look at the code:

Class Solution {public int lengthOfLIS(int[] nums) {int result[][] = new int[nums.length + 1][nums.length]; for (int i = 0; i < nums.length + 1; i++) { for (int j = 0; j < nums.length; j++) { result[i][j] = -1; Return recursiveSearch(nums, -1, 0, result); } public int recursiveSearch(int[] nums, int preIndex, int index, int[][] result) { if (nums.length == index) { return 0; If (result[preIndex + 1][index] > -1) {return result[preIndex + 1][index]; } // If the current index number is included, the maximum length of the increment sequence int tokenLength = 0; if (preIndex < 0 || nums[index] > nums[preIndex]) { tokenLength = 1 + recursiveSearch(nums, index, index + 1, result); Int notTokenLength = recursiveSearch(nums, preIndex, index + 1, result); Result [preIndex + 1][index] = tokenLength > notTokenLength? tokenLength : notTokenLength; return result[preIndex + 1][index]; }}Copy the code

Submit OK, but the result is touching, almost the slowest, no matter in time or space, only beat about 5% of the users, then continue to optimize.

Dynamic programmingCopy the code

Assuming THAT I know the maximum increasing sequence length from nums[0] to nums[I], then for NUMs [I + 1], I simply compare all the preceding numbers and find the largest increasing subsequence of all the preceding numbers less than nums[I + 1]. An additional 1 is the maximum increasing subsequence for NUMs [I + 1].

So I just have to record one more maximum, and I can figure out the maximum increment sequence for the entire array.

Let’s look at the code:

class Solution { public int lengthOfLIS(int[] nums) { if (nums.length == 0) { return 0; Int [] dp = new int[nums.length]; int[] dp = new int[nums.length]; Int Max = 1; int Max = 1; For (int I = 0; i < dp.length; Int currentMax = 0; for (int j = 0; j < i; // if nums[I] is larger than nums[j], then nums[I] can be added to nums[j]. If (nums[I] > nums[J]) {currentMax = Math.max(currentMax, dp); } // add the current number dp[I] = currentMax + 1; max = Math.max(dp[i], max); } return max; }}Copy the code

Commit OK, execution time: 9 ms, only beat 75.15% of Java commits, looks like it can continue optimization.

Greedy algorithm + binary search

A greedy algorithm means it doesn’t have to be the perfect result, just valid for the moment.

When we were constructing an increasing sequence, we were actually constantly updating it based on the previous values, and it was very accurate. But that doesn’t have to be the case, as long as each number in the sequence is relatively small, you can get the final maximum length.

Or in the,9,2,5,3,7,101,18,4,8,6,12 [10], for example:

  1. From 10 to 2, you can’t make any of them, because each one is smaller than the previous one.
  2. When you start with the smallest 2,2, 5,2, 3Both can be used as increasing sequences, but clearly feel2, 3It works better because 3 is smaller.
  3. Since 7 is greater than 3, the increasing sequence grows to2,3,7.
  4. Since 101 is also greater than 7, the increasing sequence grows to2,3,7,101.
  5. Because 18 is less than 101, but it’s greater than 7, so we can replace 101 with 18, because 18 is smaller, so the sequence updates to be2,3,7,18
  6. So now we have 4,4 is greater than 3 but less than 7, so we can replace 7 with that, even though it’s a new sequence2,3,4,18It’s not really the result, but first of all, there is no problem with the length, and secondly, if there is a new number that can be ranked last, it must be greater than 4, because it must be greater than the current maximum of 18. The sequence is updated as2,3,4,18.
  7. Similarly, 8 is greater than 4 and less than 18, so if I replace 18, that’s my new sequence2,3,4,8Is this starting to make sense to you?
  8. When 6 is encountered, update to2,3,4,6.
  9. When 12 is encountered, update to2,3,4,6,12.

And that gives us our final answer.

So if you combine that with the O(nlogn) in the instructions, then you can think of binary search, which applies here to finding the right place for the current number.

Let’s look at the code:

class Solution { public int lengthOfLIS(int[] nums) { if (nums.length == 0) { return 0; Int [] result = new int[nums.length]; int[] result = new int[nums.length]; result[0] = nums[0]; // The length of the empty array int resultLength = 1; For (int I = 1; i < nums.length; i++) { int num = nums[i]; If (num > result[resultLength -1]) {result[resultLength] = num; if (num > result[resultLength -1]) {result[resultLength] = num; resultLength++; continue; If (num == result[resultleng-1]) {continue; if (num == result[resultleng-1]) {continue; Int shouldIndex = array. binarySearch(result, 0, resultLength, num); if (shouldIndex < 0) { shouldIndex = -(shouldIndex + 1); } // the result is not necessarily the final result, but the resultLength does not change, and even if the resultLength increases, it is still relatively correct. Is a relatively small number result[shouldIndex] = num; } return resultLength; }}Copy the code

Submit OK, execution time: 2 ms, almost.

conclusion

This is the problem I solved the process, I don’t know if you understand. This problem can be solved by dynamic programming, but in order to optimize, you need greedy algorithms and binary search.

If you are interested, you can visit my blog or pay attention to my public number and headline number. Maybe there will be unexpected surprises.

death00.github.io/

Public account: The road to health