Наибольшая последовательная подпоследовательность, обратная подпоследовательность и длина

Question

У меня есть функция, которая возвращает длину подпоследовательности, но мне также нужно возвращать саму подпоследовательность, но у меня возникают проблемы с тем, чтобы заставить ее работать.

Я пробовал следующий код, но подпоследовательность возвращается правильно, только если это самая первая подпоследовательность, которая является самой длинной.

Если я использую следующий массив, длина 10 верна, но она возвращает неверная подпоследовательность [1, 2, 3, 4, 10, 11, 12, 13, 14, 15]

        int n = arr.length; 


        HashSet<Integer> S = new HashSet<Integer>(); 
        HashSet<Integer> Seq = new HashSet<Integer>(); 
        int ans = 0; 

        // Hash all the array elements 
        for (int i = 0; i < n; i++) {
            S.add(arr[i]); 
        }
        System.out.println(S);
        // check each possible sequence from the start 
        // then update optimal length 
        for (int i = 0; i < n; ++i) 
        { 
            System.out.println("ARR " + i);

            // if current element is the starting 
            // element of a sequence 
            if (!S.contains(arr[i]-1)) 
            { 
                //System.out.println("INSIDE .CONTAINS");
                // Then check for next elements in the 
                // sequence 
                int j = arr[i]; 
                int t = 0;
                while (S.contains(j)) { 
                    System.out.println("ANS " + ans);                 
                    t++;
                    if (t > ans ) { Seq.add(j);}
                    j++; 
                   // System.out.println("T " + t);

                  //  System.out.println("SEQ <<<<<<< " + Seq );
                }
                // update  optimal length if this length 
                // is more 
                if (ans < j-arr[i]) {
                    ans = j-arr[i]; 
                }  
            } 
        } 
        System.out.println(Seq);
        System.out.println(ans);

        return ans;

Answer 1

Это кажется довольно окольным способом определения последовательности.

Я полагаю, что один из ваших fl aws здесь:

// if current element is the starting 
// element of a sequence 
if (!S.contains(arr[i]-1)) 
{ 

Это определенно некорректно. Допустим, у вас есть входная последовательность {1,3,5,2,4,6}. В этом списке нет последовательностей из 2 или более. Тем не менее, входные данные от 2 до 6 будут проходить ваш тест S.contains(arr[i]-1), так как S HashSet содержит 1,2,3,4,5,6.

Вот то, что я считаю гораздо более простым способом найти самую длинную последовательность:

int longestLength = 0;
int longestStart = 0;
int currentStart = 0;
int currentLength = 1;

for(int i=1;i<arr.length;i++)
{
     if (arr[i] == arr[i-1] + 1)
     {
         // this element is in sequence.
         currentLength++;
         if (currentLength > longestLength)
         {
             longestLength = currentLength;
             longestStart = currentStart;
         }
     }
     else
     {
          // This element is not in sequence.
         currentStart = i;
         currentLength = 1;
     }
}
System.out.printlng(longestStart + ", " + longestLength);