largest subarray from array

1#include <iostream>
2#include <vector>
3using namespace std;
4 
5// Function to check if subarray `A[i…j]` is formed by consecutive integers.
6// Here, `min` and `max` denote the minimum and maximum element in the subarray.
7bool isConsecutive(int A[], int i, int j, int min, int max)
8{
9    // for an array to contain consecutive integers, the difference
10    // between the maximum and minimum element in it should be exactly `j-i`
11    if (max - min != j - i) {
12        return false;
13    }
14 
15    // create a visited array (we can also use a set)
16    vector<bool> visited(j - i + 1);
17 
18    // traverse the subarray and check if each element appears only once
19    for (int k = i; k <= j; k++)
20    {
21        // if the element is seen before, return false
22        if (visited[A[k] - min]) {
23            return false;
24        }
25 
26        // mark the element as seen
27        visited[A[k] - min] = true;
28    }
29 
30    // we reach here when all elements in the array are distinct
31    return true;
32}
33 
34// Find the largest subarray formed by consecutive integers
35void findMaxSubarray(int A[], int n)
36{
37    int len = 1;
38    int start = 0, end = 0;
39 
40    // consider each subarray formed by `A[i…j]`
41 
42    // `i` denotes the beginning of the subarray
43    for (int i = 0; i < n - 1; i++)
44    {
45        // stores the minimum and maximum element in subarray `A[i…j]`
46        int min_val = A[i], max_val = A[i];
47 
48        // `j` denotes the end of the subarray
49        for (int j = i + 1; j < n; j++)
50        {
51            // update the minimum and maximum elements of the subarray
52            min_val = min(min_val, A[j]);
53            max_val = max(max_val, A[j]);
54 
55            // check if subarray `A[i…j]` is formed by consecutive integers
56            if (isConsecutive(A, i, j, min_val, max_val))
57            {
58                if (len < max_val - min_val + 1)
59                {
60                    len = max_val - min_val + 1,
61                    start = i, end = j;
62                }
63            }
64        }
65    }
66 
67    // print the maximum length subarray
68    cout << "The largest subarray is [" << start << ", " << end << "]";
69}
70 
71int main()
72{
73    int A[] = { 2, 0, 2, 1, 4, 3, 1, 0 };
74    int n = sizeof(A) / sizeof(A[0]);
75 
76    findMaxSubarray(A, n);
77 
78    return 0;
79}