Answers for "Find largest sub-array formed by consecutive integers"

0

Find largest sub-array formed by consecutive integers

def isConsecutive(A, i, j, min, max):
 
    # for a list 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 list (we can also use a set)
    visited = [False] * (j - i + 1)
 
    # traverse the sublist and check if each element appears
    # only once
    for k in range(i, j + 1):
 
        # 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 list are distinct
    return True
 
 
# Find the largest sublist formed by consecutive integers
def findMaxSublist(A):
 
    length = 1
    start = end = 0
 
    # consider each sublist formed by `A[i…j]`
 
    # `i` denotes the beginning of the sublist
    for i in range(len(A) - 1):
 
        # stores the minimum and maximum element formed by `A[i…j]`
        min_val = A[i]
        max_val = A[i]
 
        # `j` denotes the end of the sublist
        for j in range(i + 1, len(A)):
            # update the minimum and maximum elements of the sublist
            min_val = min(min_val, A[j])
            max_val = max(max_val, A[j])
 
            # check if `A[i…j]`is formed by consecutive integers
            if isConsecutive(A, i, j, min_val, max_val):
                if length < max_val - min_val + 1:
                    length = max_val - min_val + 1
                    start = i
                    end = j
 
    # print the maximum length sublist
    print("The largest sublist is", (start, end))
Posted by: Guest on February-02-2021

Code answers related to "Find largest sub-array formed by consecutive integers"

Browse Popular Code Answers by Language