Find the longest contiguous alternating sequence

user_13290322 0
Viewed 503

Lets say we have an array {1, 1, 2, 3, 6, 5, 5, 4, 6}

Find the longest contiguous odd/even or even/odd subsequence in the array.

Answer is 5: {1, 2, 3, 6, 5}

My idea is to find two subsequence

  1. starting number is odd
  2. starting number is even

return the max of both

The code i wrote finds the longest subsequence, but is not contiguous

public static int longestAlternativeSequence(int[] a, int n) {
    int maxOdd = 0; //Max subsequence starting with odd Number
    int maxEven = 0; //Max subsequence starting with even Number
    int odd = 0;
    int even = 0;
    
    for (int i = 0; i < n; i++) {
        if (odd == 0) { // first number has to be odd
            if (a[i] % 2 == 1) {
                odd = 1;
                maxOdd++;
            }
        }
        
        else {
            if (a[i] % 2 == 0) {
                odd = 0;
                maxOdd++;
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        if (even == 0) { //first number has to be even
            if (a[i] % 2 == 0) {
                even = 1;
                maxEven++;
            }
        }
        else {
            if (a[i] % 2 == 1) {
                even = 1;
                maxEven++;
            }
        }
    }
    return Math.max(maxOdd, maxEven);
}
public static void main(String[] args) {
    int a[] = {1, 1, 2, 3, 6, 5, 5, 4, 6};
    int n = a.length; 
    System.out.println(longestOddEven(a, n)); //returns 6
}
subsequence arrays algorithm java
4 Answers

I tested for a few cases and hope this will work for you:

public static int longestAlternativeSequence(int[] a, int n){
    if (n == 0) return 0;

    boolean isOdd = a[0] % 2 == 1;
    int tempCount = 1;
    int res = 0;

    for (int i = 1; i < n; ++i){
        if ((isOdd && a[i] % 2 == 0) || (!isOdd && a[i] % 2 == 1)){
            ++tempCount;
            isOdd = a[i] % 2 == 1;
        }else{
            res = Math.max(tempCount, res);
            tempCount = 1;
        }
    }

    res = Math.max(tempCount, res);
    return res;
}

Basically what we have here is that tracking previous number's status (odd or even) and compare it with current number. If the case is true, we keep counting with temporary counter. If not, then we check whether tempCount is bigger than res or not, and reset tempCount.

If array is empty, it returns zero, otherwise it will return at least one because anyway single odd or even number complies the case.

Lastly, if correct answer ends with last element of the array, then else clause is not reachable for one last check, that is why we need to update res after looping.

user_129747350

This is just for fun. If you don't like it, ignore it.

static final Pattern ZERO_ONE_SEQUENCE = Pattern.compile("1?(01)*0?");

static int[] longestOddEvenSubsequence(int[] input) {
    String binaryString = Arrays.stream(input)
        .mapToObj(intValue -> Integer.toString(intValue & 1))
        .collect(Collectors.joining());
    return ZERO_ONE_SEQUENCE.matcher(binaryString).results()
        .map(m -> Arrays.copyOfRange(input, m.start(), m.end()))
        .max(Comparator.comparing(intArray -> intArray.length))
        .get();
}

and

System.out.println(Arrays.toString(
    longestOddEvenSubsequence(new int[] {1, 1, 2, 3, 6, 5, 5, 4, 6})));
// -> [1, 2, 3, 6, 5]
Admin1

How about this one here? It uses recursion and memoization. It is a different approach and might be an overkill for this task, but it does more or less the same as the for-loop-solution. It really depends on what you want to do with it and if you want to extend it further later on.

I have also added a few test cases below including negative integers.

public static int maxEvenOddContinousSequence(int[] a) {
    final int numElements = a.length;
    int result;
    if (numElements == 0) {
        result = 0;
    } else if (numElements == 1) {
        result = 1;
    } else {
        result = findEvenOddContinousSubsequence(a, numElements, 0, a[0] % 2 == 0, 0, 0);
    }
    return result;
}

private static int findEvenOddContinousSubsequence(int[] a, int numElements, int index, boolean isEven, int currentLongestSequence, int longestSequence) {
    if (index < numElements) {
        final int currentElement = Math.abs(a[index]);
        final int currentElementMod2 = currentElement % 2;
        if (currentElementMod2 == (isEven ? 0 : 1)) {
            return findEvenOddContinousSubsequence(a, numElements, ++index, !isEven, ++currentLongestSequence, longestSequence);
        } else {
            return findEvenOddContinousSubsequence(a, numElements, index, currentElementMod2 == 0, 0, Math.max(currentLongestSequence, longestSequence));
        }
    }
    return Math.max(currentLongestSequence, longestSequence);
}

public static void main(String[] args) {
    int a[] = {};
    int b[] = {1};
    int c[] = {1, 2};
    int d[] = {1, 1, 2, 3, 6, 5};
    int e[] = {1, 1, 3, 3, 6, 5, 2, 5, 2, 4, 6};
    int f[] = {0, -1, -3, -6, -5, -2};
    System.out.println("A:" + maxEvenOddContinousSequence(a)); // expected: 0 => []
    System.out.println("B:" + maxEvenOddContinousSequence(b)); // expected: 1 => [1]
    System.out.println("C:" + maxEvenOddContinousSequence(c)); // expected: 2 => [1, 2]
    System.out.println("D:" + maxEvenOddContinousSequence(d)); // expected: 5 => [1, 2, 3, 6, 5]
    System.out.println("E:" + maxEvenOddContinousSequence(e)); // expected: 6 => [3, 6, 5, 2, 5, 2]
    System.out.println("F:" + maxEvenOddContinousSequence(f)); // expected: 4 => [-3, -6, -5, -2]
}

Output: A:0 B:1 C:2 D:5 E:6 F:4

user_12942830

This function will return start and next-to-last index of required interval. It's based on simple idea of checking the current and the previous. Note, the i <= arr.length condition, as it deals with case when the interval runs till the end. This case is checked in if.

static int[] contAlternating(int[] arr) {
            if (arr == null || arr.length == 0)
                return null;
            if (arr.length == 1)
                return new int[] { 0, 1 };
            int lastStart = 0;
            int maxStart = 0;
            int maxEnd = 1;
            for (int i = 1; i <= arr.length; i++) {
                if ((i < arr.length)
                        && ((arr[i] % 2 == 0 && arr[i - 1] % 2 == 1) || (arr[i] % 2 == 1 && arr[i - 1] % 2 == 0))) {
                    continue;
                }
                if (i - lastStart > maxEnd - maxStart) {
                    maxStart = lastStart;
                    maxEnd = i;
                }
                lastStart = i;
            }
            return new int[] { maxStart, maxEnd };
        }
user_125906390
Related