当前位置：网站首页>[array] longest continuous subsequence in nc95 array - difficult

[array] longest continuous subsequence in nc95 array - difficult

2022-07-23 23:23:00 【51CTO】

NC95 Longest continuous subsequence in array

Knowledge point Union checking set Array

describe

Given an unordered array arr, Returns the length of the longest continuous sequence ( The required value is continuous , The position can be discontinuous , for example 3,4,5,6 Is a continuous natural number ）

Data range ： , The values in the array meet

requirement ： Spatial complexity , Time complexity

Example 1

Input ：

       
       [100,4,200,1,3,2]
      
1.

Return value ：

Example 2

Input ：

Return value ：

Answer key

Sort + Statistics

Ideas ：

Sort the array first , Then count consecutive numbers . Be careful , If it's continuous 2 Two numbers are equal , The continuous length should not be reset at this time .

Similar to this solution, there are also uses set Store all elements and make statistics , Or use hash Table statistics ~~

The code is as follows ：

       
       #include <bits/stdc++.h>
       
       using 
       
       namespace 
       
       std;
       
       int 
       
       MLS(
       
       vector
       
       <
       
       int
       
       > 
       
       &
       
       arr)
       
{
       
       if (
       
       arr.
       
       size() 
       
       <= 
       
       1)
       
  {
       
       return 
       
       arr.
       
       size();
       
  }
       
       std::sort(
       
       arr.
       
       begin(), 
       
       arr.
       
       end());
       
       int 
       
       ans 
       
       = 
       
       1;
       
       int 
       
       len 
       
       = 
       
       1;
       
       for (
       
       int 
       
       i 
       
       = 
       
       1; 
       
       i 
       
       < 
       
       arr.
       
       size(); 
       
       ++
       
       i)
       
  {
       
       if (
       
       arr[
       
       i 
       
       - 
       
       1] 
       
       + 
       
       1 
       
       == 
       
       arr[
       
       i])
       
    {
       
       len
       
       ++;
       
       ans 
       
       = 
       
       std::max(
       
       len, 
       
       ans);
       
       continue;
       
    }
       
       else 
       
       if (
       
       arr[
       
       i 
       
       - 
       
       1] 
       
       == 
       
       arr[
       
       i])
       
    {
       
       continue;
       
    }
       
       else
       
    {
       
       len 
       
       = 
       
       1;
       
    }
       
  }
       
       return 
       
       ans;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.