最大连续子序列，return个子序列和长度

Question

我有一个函数 return 是子序列的长度，但我还需要 return 子序列本身，但我无法让它工作。

我已经尝试了以下代码，但只有第一个最长的子序列才 return 是正确的。

如果我使用以下数组，10 的长度是正确的，但它 return 是 [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

这似乎是一种相当迂回的确定顺序的方法。

我认为你的缺点之一是：

// 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);

最大连续子序列，return个子序列和长度

Largest consecutive subsequence, return subsequence and length

java

algorithm

subsequence