Largest consecutive subsequence, return subsequence and length

Question

I have a function that returns the length of the subsequence but I also need to return the subsequence itself but i'm having trouble getting it to work.

I have tried the following code but the subsequence only returns correctly if it's the first subsequence that is the longest.

If I use the following array the length of 10 is correct but it returns an incorrect subsequence of [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

That seems like a rather roundabout way of determining a sequence.

I believe one of your flaws is here:

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

This is definitely flawed. Let's say you have the input sequence {1,3,5,2,4,6}. There are no sequences of 2 or more in that list. However, inputs from 2 to 6 would pass your test of S.contains(arr[i]-1), as the S HashSet contains 1,2,3,4,5,6.

Here is what I would consider a much simpler way to find the longest sequence:

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