Рубрики

Длина наибольшего подмассива с непрерывными элементами | Комплект 1

Учитывая массив различных целых чисел, найдите длину самого длинного подмассива, который содержит числа, которые могут быть расположены в непрерывной последовательности.

Примеры:

Input:  arr[] = {10, 12, 11};
Output: Length of the longest contiguous subarray is 3

Input:  arr[] = {14, 12, 11, 20};
Output: Length of the longest contiguous subarray is 2

Input:  arr[] = {1, 56, 58, 57, 90, 92, 94, 93, 91, 45};
Output: Length of the longest contiguous subarray is 5

Мы настоятельно рекомендуем свернуть браузер и попробовать это в первую очередь.

Важно отметить, что все элементы различны. Если все элементы различны, то подмассив имеет смежные элементы тогда и только тогда, когда разность между максимальным и минимальным элементами в подмассиве равна разнице между последним и первым индексами подмассива. Таким образом, идея состоит в том, чтобы отслеживать минимальный и максимальный элемент в каждом подмассиве.

Ниже приведена реализация вышеприведенной идеи.

C ++

#include<iostream>

using namespace std;

  
// Сервисные функции для поиска минимума и максимума
// два элемента

int min(int x, int y) { return (x < y)? x : y; }

int max(int x, int y) { return (x > y)? x : y; }

  
// Возвращает длину самого длинного непрерывного подмассива

int findLength(int arr[], int n)

{

    int max_len = 1;  // Инициализировать результат

    for (int i=0; i<n-1; i++)

    {

        // Инициализируем min и max для всех подмассивов, начиная с i

        int mn = arr[i], mx = arr[i];

  

        // Рассмотрим все подмассивы, начиная с i и заканчивая j

        for (int j=i+1; j<n; j++)

        {

            // Обновляем min и max в этом подмассиве, если это необходимо

            mn = min(mn, arr[j]);

            mx = max(mx, arr[j]);

  

            // Если текущий подмассив имеет все смежные элементы

            if ((mx - mn) == j-i)

                max_len = max(max_len, mx-mn+1);

        }

    }

    return max_len;  // Возвращаем результат

}

  
// Программа драйвера для проверки вышеуказанной функции

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;

}

Джава

class LargestSubArray2 

{

    // Сервисные функции для поиска минимума и максимума

    // два элемента

  

    int min(int x, int y) 

    {

        return (x < y) ? x : y;

    }

  

    int max(int x, int y) 

    {

        return (x > y) ? x : y;

    }

  

    // Возвращает длину самого длинного непрерывного подмассива

    int findLength(int arr[], int n) 

    {

        int max_len = 1// Инициализировать результат

        for (int i = 0; i < n - 1; i++) 

        {

            // Инициализируем min и max для всех подмассивов, начиная с i

            int mn = arr[i], mx = arr[i];

  

            // Рассмотрим все подмассивы, начиная с i и заканчивая j

            for (int j = i + 1; j < n; j++) 

            {

                // Обновляем min и max в этом подмассиве, если это необходимо

                mn = min(mn, arr[j]);

                mx = max(mx, arr[j]);

  

                // Если текущий подмассив имеет все смежные элементы

                if ((mx - mn) == j - i)

                    max_len = max(max_len, mx - mn + 1);

            }

        }

        return max_len;  // Возвращаем результат

    }

  

    public static void main(String[] args) 

    {

        LargestSubArray2 large = new LargestSubArray2();

        int arr[] = {1, 56, 58, 57, 90, 92, 94, 93, 91, 45};

        int n = arr.length;

        System.out.println("Length of the longest contiguous subarray is "

                + large.findLength(arr, n));

    }

}

  
// Этот код предоставлен Mayank Jaiswal

python3

# Python3 программа для определения длины
# самого длинного подмассива

  
# Сервисные функции, чтобы найти минимум
# и максимум двух элементов

def min(x, y):

    return x if(x < y) else y

      

def max(x, y):

    return x if(x > y) else y

  
# Возвращает длину самого длинного
# смежный подмассив

def findLength(arr, n):

      

    # Инициализировать результат

    max_len = 1 

    for i in range(n - 1):

      

        # Инициализировать мин и макс для

        # все подмассивы, начинающиеся с i

        mn = arr[i]

        mx = arr[i]

  

        # Рассмотрим все подмассивы, начинающиеся

        # с I и заканчивая J

        for j in range(i + 1, n):

          

            # Обновление мин и макс в

            # этот подмассив при необходимости

            mn = min(mn, arr[j])

            mx = max(mx, arr[j])

  

            # Если текущий подмассив имеет

            # все смежные элементы

            if ((mx - mn) == j - i):

                max_len = max(max_len, mx - mn + 1)

          

    return max_len

  
Код водителя

arr = [1, 56, 58, 57, 90, 92, 94, 93, 91, 45]

n = len(arr)

print("Length of the longest contiguous subarray is ",

                                    findLength(arr, n))

                                      
# Этот код предоставлен Anant Agarwal.

C #

using System;

  

class GFG {

      

    // Возвращает длину самого длинного

    // смежный подмассив

    static int findLength(int []arr, int n) 

    {

        int max_len = 1; // Инициализировать результат

        for (int i = 0; i < n - 1; i++) 

        {

            // Инициализировать мин и макс для всех

            // подмассивы начинающиеся с i

            int mn = arr[i], mx = arr[i];

  

            // Рассмотрим все подмассивы, начинающиеся

            // с i и заканчивая j

            for (int j = i + 1; j < n; j++) 

            {

                // Обновляем мин и макс в этом

                // подрешетка при необходимости

                mn = Math.Min(mn, arr[j]);

                mx = Math.Max(mx, arr[j]);

  

                // Если у текущего подмассива есть все

                // смежные элементы

                if ((mx - mn) == j - i)

                    max_len = Math.Max(max_len,

                                  mx - mn + 1);

            }

        }

        return max_len; // Возвращаем результат

    }

  

    public static void Main() 

    {

          

        int []arr = {1, 56, 58, 57, 90, 92,

                               94, 93, 91, 45};

        int n = arr.Length;

          

        Console.WriteLine("Length of the longest"

                     + " contiguous subarray is "

                           + findLength(arr, n));

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php
// Сервисные функции для поиска минимума
// и максимум из двух элементов

function mins($x, $y)

{

    if($x < $y

        return $x;

    else

        return $y;

}

      

function maxi($a, $b)

{

    if($a > $b

        return $a;

    else

        return $b;

}

      
// Возвращает длину самого длинного
// смежный подмассив

function findLength(&$arr, $n)

{

    $max_len = 1; // Инициализировать результат

    for ($i = 0; $i < $n - 1; $i++)

    {

        // Инициализировать мин и макс для всех

        // подмассивы начинающиеся с i

        $mn = $arr[$i];

        $mx = $arr[$i];

  

        // Рассмотрим все подмассивы, начинающиеся

        // с i и заканчивая j

        for ($j = $i + 1; $j < $n; $j++)

        {

            // Обновляем мин и макс в этом

            // подрешетка при необходимости

            $mn = mins($mn, $arr[$j]);

            $mx = maxi($mx, $arr[$j]);

  

            // Если у текущего подмассива есть все

            // смежные элементы

            if (($mx - $mn) == $j - $i)

                $max_len = maxi($max_len,

                                $mx - $mn + 1);

        }

    }

    return $max_len; // Возвращаем результат

}

  
// Код драйвера

$arr = array(1, 56, 58, 57, 90, 

             92, 94, 93, 91, 45);

$n = sizeof($arr);

echo ("Length of the longest contiguous"

                         " subarray is ");

echo (findLength($arr, $n));

      
// Этот код добавлен
// от Shivi_Aggarwal.
?>

Выход:

Length of the longest contiguous subarray is 5

Временная сложность вышеуказанного решения составляет O (n 2 ).

Вскоре мы рассмотрим решение проблемы, когда дублирующие элементы допускаются в подмассиве.

Длина наибольшего подмассива с непрерывными элементами | Набор 2

Эта статья предоставлена Арджуном . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Длина наибольшего подмассива с непрерывными элементами | Комплект 1

0.00 (0%) 0 votes