# Question 5 – Find Largest Sub-array #### Question 5

You are given an unsorted array of integers. You  need to find the largest sub-array formed by consecutive numbers. The sub-array should only contain unique values. For example

Input: {2, 7, 2, 1, 4, 3, 5, 0}

Output: The largest subarray is from index 2 to 7

The sub-array is {2, 1, 4, 3, 5}

#### Solution

The approach is to iterate through the array. Then we keep track of the largest sub-array seen so far. We also make sure that the integers in the sub-array is consecutive.

For the sub-array elements to be consecutive, then:

• the difference between the largest and smallest element must be equal to the length of the sub-array minus one
• we check the the elements are unique track tracking the already visited element in another array.

The Java code is given below:

```/*
* Find the largest consecutive sub-array
* Written by: Kindson The Genius
*/
public class LargestSubarray {

//helper function to check if sub-array is consecutive
static boolean isConsecutive(int A[], int i, int j, int min, int max)
{
if(max - min != j - i) {
return false;
}

//track the visited elements
boolean visited[] = new boolean[j - i + 1];

for(int k = i; k <= j; k++) {
if(visited[A[k] - min]) {
return false;
}

visited[A[k] - min] = true;
}
return true;
}

public static void findMaxSubarray(int[] A) {
int len = 1;
int start = 0;
int end = 0;

//Loop through all the elements of the array
for(int i = 0; i < A.length - 1; i++) {
int min_val = A[i];
int max_val = A[i];

//Loop through the current sub-array
for(int j = i; j < A.length; j++)
{
min_val = Math.min(min_val, A[j]);
max_val = Math.max(max_val, A[j]);

//check the the elements are consecutive
if(isConsecutive(A, i, j, min_val, max_val)) {
if(len < max_val - min_val + 1) {
len = max_val - min_val + 1;
start = i;
end = j;
}
}
}
}

System.out.println("The largest subarray is from index "
+ start + " to " + end);
}

//Test the program
public static void main(String[] args) {
int[] A = {2, 7, 2, 1, 4, 3, 5, 0};
findMaxSubarray(A);
}

}
```