Find the longest increasing subsequence

Description: Given an unsorted array of integers, find the longest continuously increasing subsequence and return the length of the sequence.

Continuously increasing subsequences can be determined by two subscripts L and r (l < r), if for every L <= I < r, nums[I] < nums[I + 1], Then the subsequence [NUMs [L], NUMs [L + 1]…, NUMs [r-1], NUMs [r]] is a continuous increasing subsequence.

Source: LeetCode link: leetcode-cn.com/problems/lo… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Js code attached:

/ * * *@param {number[]} numArr
 * @return {number}* /
var findLengthOfLCIS = function(numArr) {
  NumArr = numArr = numArr = numArr = numArr
  // But in the spirit of pure functions, forget it
  if (0===numArr.length) {
    return 0
  }
  let lengthResult = [];
  let start = -1;
  for (let i = 0; i < numArr.length; i++) {
    let next = i + 1;
    if (numArr[i]<numArr[next]) {
      continue;
    } else{ lengthResult.push(i - start); start = i; }}// Find the maximum value of this array
  let maxValue = lengthResult[0]
  for (let i = 1; i < lengthResult.length; i++) {let nextValue = lengthResult[i];
    maxValue = maxValue > nextValue ? maxValue : nextValue;
  }
  // return maxValue;
  return maxValue;
  // lengthResult
}
Copy the code

Execution Result:

Execution time: 100 ms, beat 16.02% user memory consumption: 39.9 MB, beat 12.98% user memory consumption: 39.9 MB, beat 12.98% user memory consumption:Copy the code

After my optimization: complete code

/ * * *@param {number[]} numArr
 * @return {number}* /
var findLengthOfLCIS = function(numArr) {
  if (0===numArr.length) {
    return 0;
  }
  let start = -1;
  let max=0; // This is the longest increasing subsequence required
  for (let i = 0; i < numArr.length; i++) {
    if (numArr[i]<numArr[1+i]) {
      continue;
    } else{ max = i - start > max ? i - start : max; start = i; }}return max;
}
Copy the code

The results show:

Execution result: By displaying details96Ms, beat out all JavaScript submissions23.84% user memory consumption:38.8MB, beat out all JavaScript submissions37.60% of users show off:Copy the code

Take a look at the 64ms code

var findLengthOfLCIS = function(nums, l = 1, r = 1) {
    return nums.length ? (nums.reduce((p, v) = > (v > p ? r = Math.max(r, ++l) : l = 1, v)), r) : 0
};
Copy the code

I was a little disappointed when I saw how long it took after optimization, but when I saw that my code had no features at all and could have been written in C ++, I decided to write in C because it was a hassle to write classes in C ++

Source code display:

int findLengthOfLCIS(int* nums, int numsSize){
    if(0==numsSize){
        return 0;
    }
    int start = - 1;
    int max = 0;
    int tags = 0;
    for(int i=0; i<numsSize; ++i){if(numsSize- 1! =i && nums[i]<nums[1+i]){
            ++tags;
            max = i-start > max ? i-start : max ;
            continue;
        }else{ max = i-start > max ? i-start : max ; start = i; }}if(numsSize- 1==tags){
        return tags+1;
    }
    return max;
}
Copy the code

The results are as follows:

Execution result: By displaying details Execution time: 12 ms, beat 63.24% of users in all C commits memory consumption: 6.3 MB, beat 62.29% of users in all C commitsCopy the code

This may need to be optimized

See someone else’s 4MS code again:

int findLengthOfLCIS(int* nums, int numsSize){
    int sum = 0;
    int start = 0;
    for (int i = 0; i < numsSize; i++) {
        if (i > 0 && nums[i] <= nums[i - 1]) {
            start = i;
        }
        if(i - start + 1 > sum){
            sum = i - start + 1; }}return sum;
}
Copy the code

C + + implementation:

// Longge solves the longest increasing subsequence
#include <cstdio>
#include <algorithm>
using namespace std;

int a[40005];
int d[40005];

int main(a)
{
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    scanf("%d", &a[i]);
  if (n == 0)
  { //0 elements
    printf("0\n");
    return 0;
  }
  d[1] = a[1]; / / initialization
  int len = 1;
  for (int i = 2; i <= n; i++)
  {
    If len is the longest ascending subsequence, this becomes >
    if (a[i] >= d[len])
      d[++len] = a[i];
    else
    { // If not, replace it with the most appropriate one
      // Find the first subscript of d greater than it. If it is the longest ascending subsequence, change this to lower_bound
      int j = upper_bound(d + 1, d + len + 1, a[i]) - d; d[j] = a[i]; }}printf("%d\n", len);
  return 0;
}
Copy the code