Max Common Array Slice in Java

You are given a sequence of n integers a0, a1, . . . , an−1 and the task is to find the maximum slice of the array which contains no more than two different numbers.

Input 1 :

[1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 6, 2, 1, 8]

Result 1 : Answer is 10 because the array slice of (0, 9) is the largest slice of the array with no more than two different numbers.

- There are 10 items in this slice which are "1, 1, 1, 2, 2, 2, 1, 1, 2, 2".
- 2 different numbers for this slice are 1 and 2.


Input 2:

[53, 800, 0, 0, 0, 356, 8988, 1, 1]

Result 2: Answer is 4 because the slice of (1, 4) is the largest slice of the array with no more than two different numbers. The slice (2, 5) would also be valid and would still give a result of 4.

- There are 4 items in this slice which are "800,0,0,0".
- 2 different numbers for this slice are 800 and 0.

Maximum common array slice of the array which contains no more than two different numbers implementation in Java takes a comma delimited array of numbers from STDIN and the output is written back to console.

Important thing here is that we used HashMap data structure from "java.util.HashMap" package.

package com.arrayutilities;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class MaxCommonArraySlice {

 public static int maxCommonArraySlice(int[] array) {
  Map<Integer, Integer> items = new HashMap<Integer, Integer>();
  int result = 0;
  int startIndex = 0;
  int uniqueItemCount = 0;
  while (startIndex < array.length) {
   items.put(array[startIndex], startIndex);
   uniqueItemCount = uniqueItemCount + 1;
   for (int j = startIndex + 1; j < array.length; j++) {
    if (items.get(array[j]) == null) {
     if (uniqueItemCount != 2) {
      items.put(array[j], j);
      uniqueItemCount = uniqueItemCount + 1;
      if (j == array.length - 1) {
       result = Math.max(result, j - startIndex + 1);
       startIndex = array.length;
       break;
      }
     } else if (uniqueItemCount == 2) {
      result = Math.max(result, j - startIndex);
      int item = array[j-1];
      int firstFoundIndex = 0;
      for( int k=j-1; k>=0; k-- )
      {
       if( array[k] != item )
       {
        firstFoundIndex = k+1;
        break;
       }
      }
      startIndex = firstFoundIndex;
      items.clear();
      uniqueItemCount = 0;
      break;
     }
    } else if (items.get(array[j]) != null) {
     if (j == array.length - 1) {
      result = Math.max(result, j - startIndex + 1);
      startIndex = array.length;
      break;
     }
    }
   }
  }

  return result;
 }

 public static void main(String[] args) {

  Scanner in = new Scanner(System.in);
  String line = in.nextLine();
  if (!line.equals("")) {
   if (line.length() == 1) {
    System.out.println("1");
   } else {
    try {
     line = line.replaceAll("\\s+", "");
     String[] items = line.split(",");
     int N = items.length;
     int[] input = new int[N];

     for (int i = 0; i < N; i++)
      input[i] = Integer.valueOf(items[i]);

     if (input.length == 1) {
      System.out.println("1");
     } else {
      int result1 = maxCommonArraySlice(input);
      System.out.println(result1);
     }
    } catch (Exception ex) {
     System.out.println(ex.toString());
    }
   }
  }
  in.close();
 }
}

When you create a new MaxCommonArraySlice.java file and put the above code inside it with a main() method, application waits you to enter some input from the console.

Following is the console input and output :

Another console input and output of the above program :

Another console input and output of the above program :

Another console input and output of the above program :

Another console input and output of the above program :