Answers for "Largest subArray from array"

Largest subArray from array

#include <iostream>
#include <vector>
using namespace std;
 
// Function to check if subarray `A[i…j]` is formed by consecutive integers.
// Here, `min` and `max` denote the minimum and maximum element in the subarray.
bool isConsecutive(int A[], int i, int j, int min, int max)
{
    // for an array to contain consecutive integers, the difference
    // between the maximum and minimum element in it should be exactly `j-i`
    if (max - min != j - i) {
        return false;
    }
 
    // create a visited array (we can also use a set)
    vector<bool> visited(j - i + 1);
 
    // traverse the subarray and check if each element appears only once
    for (int k = i; k <= j; k++)
    {
        // if the element is seen before, return false
        if (visited[A[k] - min]) {
            return false;
        }
 
        // mark the element as seen
        visited[A[k] - min] = true;
    }
 
    // we reach here when all elements in the array are distinct
    return true;
}
 
// Find the largest subarray formed by consecutive integers
void findMaxSubarray(int A[], int n)
{
    int len = 1;
    int start = 0, end = 0;
 
    // consider each subarray formed by `A[i…j]`
 
    // `i` denotes the beginning of the subarray
    for (int i = 0; i < n - 1; i++)
    {
        // stores the minimum and maximum element in subarray `A[i…j]`
        int min_val = A[i], max_val = A[i];
 
        // `j` denotes the end of the subarray
        for (int j = i + 1; j < n; j++)
        {
            // update the minimum and maximum elements of the subarray
            min_val = min(min_val, A[j]);
            max_val = max(max_val, A[j]);
 
            // check if subarray `A[i…j]` is formed by consecutive integers
            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;
                }
            }
        }
    }
 
    // print the maximum length subarray
    cout << "The largest subarray is [" << start << ", " << end << "]";
}
 
int main()
{
    int A[] = { 2, 0, 2, 1, 4, 3, 1, 0 };
    int n = sizeof(A) / sizeof(A[0]);
 
    findMaxSubarray(A, n);
 
    return 0;
}