Longest Snake Sequence

Question

Question : A set of numbers separated by space is passed as input. The program must print the largest snake sequence present in the numbers. A snake sequence is made up of adjacent numbers such that for each number, the number on the right or left is +1 or -1 of it's value. If multiple snake sequences of maximum length is possible print the snake sequence appearing in the natural input order.

Example Input/Output 1:

Input:

5 6 7 9 8 8

Output:

5 6 7 8 9 8

8 9 8 7 6 5

Example Input/Output 2:

Input:

9 8 7 5 3 0 1 -2 -3 1 2

Output:

3 2 1 0 1

void doPermute(int[] in, StringBuffer out, boolean[] used, int length, int level, StringBuffer max) {
    if (level == length) {
        int count = 0;
        for (int i = 1; i < out.length(); i++) {
            if (Math.abs(Character.getNumericValue(out.charAt(i)) - Character.getNumericValue(out.charAt(i - 1))) != 1) {
                //System.out.println(Character.getNumericValue(i) - Character.getNumericValue(i - 1) + "  " + i + "   yes");
                count++;
                break;
            }
        }
        if (count == 0) {
            max.append(out + " ");

        }

        return;
    }
    for (int i = 0; i < length; ++i) {
        if (used[i]) {
            continue;
        }
        out.append(in[i]);
        used[i] = true;
        doPermute(in, out, used, length, level + 1, max);
        used[i] = false;
        out.setLength(out.length() - 1);
    }
}

As i am using StringBuffer my code passed the test cases that contains positive value (first test case) but failed in test cases containing negative values(second test case).

Update:- I replaced stringbuffer with Integer[] and made few changes.it works fine for smaller inputs of length 8 or 9. How to make it fast for larger inputs of length 13 to 15?

Answer 1

Your comparison isn't finding adjacent numbers for negative values. For example: Abs(-2) - (-3) = 5 but -2 and -3 should be adjacent. Ok. I see you're parsing - and digit separately. Given the requirement of what a snake sequence is, the longest snake sequence for "5 6 7 9 8 8" is "5 6 7". The output listed above does not correspond to the definition: " adjacent numbers such that for each number, the number on the right or left is +1 or -1 of it's value". How does "5 6 7 8 9 8" meet the definition of snake sequence for "5 6 7 9 8 8"? Sorry I couldn't help. You might want to parse the code into Integers, store the longest sequences in a map).

@Test
public void testSnake(){
    String t2 = "9 8 7 5 3 0 1 -2 -3 1 2";
    List<String> numsStr = Arrays.asList(t2.split(" "));
    List<Integer> nums = new ArrayList();
    HashMap<Integer,List<Integer> > numMap = new HashMap();

    numsStr.forEach((s) -> {
        Integer val = Integer.decode(s);
        nums.add(val);
    });

    nums.forEach((num) -> {
        System.out.println("num: " + num);
        // track longest sequence, store in numMap
    });
    // Print numMap
}

Answer 2

Have you tried doing the process using an array of integers?

Scanner sc = new Scanner(System.in);
String s = sc.nextLine(); //The numbers entered in string format separated by spaces
String ss = s.split(" "); //Numbers separated by space will be put as individual numbers in a String array but each number is still in string format
int l = ss.length, i = 0;
int[] n = new int[l]; //The integer array which will store the values
for(i = 0; i < l; i++)
{
    n[i] = Integer.parseInt(ss[i]);  //Has integers now instead of string numbers
}

There might be creation of a few extra arrays but then calling the Character.getNumericValue() function repeatedly can also reduce efficiency. Also might solve your StringBuffer problem.

But SkillRack is very annoying anyway.