# Given an array with all distinct elements, find the length of the longest sub-array which has elements(not in any particular order) that could form a contiguous sequence

## Algorithm

The main insight used in this algorithm is that for a given sub-array if the length of the sub-array is equal to one plus difference of values of maximum and minimum element in that sub-array then the elements in that sub-array would be able to form a contiguous sequence. This condition holds true only if the elements of the sub-array are distinct elements.

For example, for sub-array {32,34,36,33,35,37} from array {10,12,11,94,56,32,34,36,33,35,37}, maximum element in this sub-array is 37 and minimum element is 32 making the difference between them as 5. This difference of 5 plus one is equal to the length of this sub-array which is 6.

In the algorithm, we check for the condition (maxElement – minElement + 1 = length of the sub-array) for all possible sub-arrays. If this condition evaluates to true, we update the maximum length of such sub-array if required.

Time complexity for this approach is O(n^2) with O(1) extra space.

**Code->**

#include<iostream> using namespace std; // Utility functions to find minimum and maximum of // two elements int min(int x, int y) { return (x < y)? x : y; } int max(int x, int y) { return (x > y)? x : y; } // Returns length of the longest contiguous subarray int findLength(int arr[], int n) { int max_len = 1; // Initialize result for (int i=0; i<n-1; i++) { // Initialize min and max for all subarrays starting with i int mn = arr[i], mx = arr[i]; // Consider all subarrays starting with i and ending with j for (int j=i+1; j<n; j++) { // Update min and max in this subarray if needed mn = min(mn, arr[j]); mx = max(mx, arr[j]); // If current subarray has all contiguous elements if ((mx - mn) == j-i) max_len = max(max_len, mx-mn+1); } } return max_len; // Return result } // Driver program to test above function int main() { int arr[] = {1, 56, 58, 57, 90, 92, 94, 93, 91, 45}; int n = sizeof(arr)/sizeof(arr[0]); cout << "Length of the longest contiguous subarray is " << findLength(arr, n); return 0; }