Рубрики

Максимальная длина битонного субмассива | Установите 1 (O (n) время и O (n) пространство)

Для данного массива A [0… n-1], содержащего n натуральных чисел, подмассив A [i… j] является битоническим, если существует ak с i <= k <= j такой, что A [i] <= A [i + 1]… = A [k + 1]> = .. A [j — 1]> = A [j]. Напишите функцию, которая принимает массив в качестве аргумента и возвращает длину битовой подмассивы максимальной длины.
Ожидаемая временная сложность решения O (n)

Простые примеры
1) A [] = {12, 4, 78, 90, 45, 23}, максимальная битовая подрешетка составляет {4, 78, 90, 45, 23}, длина которой равна 5.

2) A [] = {20, 4, 1, 2, 3, 4, 2, 10}, максимальная длина битовой подрешетки равна {1, 2, 3, 4, 2}, которая имеет длину 5.

Экстремальные Примеры
1) A [] = {10}, единственный элемент является битноинхронным, поэтому вывод равен 1.

2) A [] = {10, 20, 30, 40}, весь массив является битоническим, поэтому вывод равен 4.

3) A [] = {40, 30, 20, 10}, весь массив битонический, поэтому вывод равен 4.

Решение
Давайте рассмотрим массив {12, 4, 78, 90, 45, 23}, чтобы понять душу.
1) Создайте вспомогательный массив inc [] слева направо так, чтобы inc [i] содержал длину неубывающего подмассива, оканчивающегося на arr [i].
Для A [] = {12, 4, 78, 90, 45, 23}, inc [] равно {1, 1, 2, 3, 1, 1}

2) Создайте другой массив dec [] справа налево так, чтобы dec [i] содержал длину не увеличивающегося подмассива, начиная с arr [i].
Для A [] = {12, 4, 78, 90, 45, 23}, dec [] равен {2, 1, 1, 3, 2, 1}.

3) Когда у нас есть массивы inc [] и dec [], все, что нам нужно сделать, — это найти максимальное значение (inc [i] + dec [i] — 1).
Для {12, 4, 78, 90, 45, 23} максимальное значение (inc [i] + dec [i] — 1) равно 5 для i = 3.

C ++

// C ++ программа для определения длины
// самый длинный битонный подмассив
#include <bits/stdc++.h>

using namespace std;

  

int bitonic(int arr[], int n) 

    // Длина увеличивающегося подмассива

    // заканчивается на всех индексах

    int inc[n]; 

      

    // Длина убывающего подмассива

    // начиная со всех индексов

    int dec[n]; 

    int i, max; 

  

    // длина возрастающей последовательности

    // конец первого индекса равен 1

    inc[0] = 1; 

  

    // длина возрастающей последовательности

    // начиная с первого индекса 1

    dec[n-1] = 1; 

  

    // Шаг 1) Построить растущий массив последовательностей

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

    inc[i] = (arr[i] >= arr[i-1])? inc[i-1] + 1: 1; 

  

    // Шаг 2) Построить убывающий массив последовательностей

    for (i = n-2; i >= 0; i--) 

    dec[i] = (arr[i] >= arr[i+1])? dec[i+1] + 1: 1; 

  

    // Шаг 3) Найти длину

    // максимальная длина битовой последовательности

    max = inc[0] + dec[0] - 1; 

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

        if (inc[i] + dec[i] - 1 > max) 

            max = inc[i] + dec[i] - 1; 

  

    return max; 

  
/ * Код водителя * /

int main() 

    int arr[] = {12, 4, 78, 90, 45, 23}; 

    int n = sizeof(arr)/sizeof(arr[0]); 

    cout << "nLength of max length Bitnoic Subarray is " << bitonic(arr, n); 

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// C программа для определения длины самого длинного битонного подмассива
#include<stdio.h>
#include<stdlib.h>

  

int bitonic(int arr[], int n)

{

    int inc[n]; // Длина увеличивающегося окончания подмассива по всем индексам

    int dec[n]; // Длина убывающего подмассива, начиная со всех индексов

    int i, max;

  

    // длина возрастающей последовательности, заканчивающейся на первом индексе, равна 1

    inc[0] = 1;

  

    // длина возрастающей последовательности, начиная с первого индекса, равна 1

    dec[n-1] = 1;

  

    // Шаг 1) Построить растущий массив последовательностей

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

       inc[i] = (arr[i] >= arr[i-1])? inc[i-1] + 1: 1;

  

    // Шаг 2) Построить убывающий массив последовательностей

    for (i = n-2; i >= 0; i--)

       dec[i] = (arr[i] >= arr[i+1])? dec[i+1] + 1: 1;

  

    // Шаг 3) Найти длину максимальной битовой последовательности

    max = inc[0] + dec[0] - 1;

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

        if (inc[i] + dec[i] - 1 > max)

            max = inc[i] + dec[i] - 1;

  

    return max;

}

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

int main()

{

    int arr[] = {12, 4, 78, 90, 45, 23};

    int n = sizeof(arr)/sizeof(arr[0]);

    printf("nLength of max length Bitnoic Subarray is %d",

            bitonic(arr, n));

    return 0;

}

Джава

// Java-программа для определения длины самого длинного битонного подмассива

import java.io.*;

import java.util.*;

  

class Bitonic

{

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

    {

        int[] inc = new int[n]; // Длина возрастающего окончания подмассива

                                // по всем показателям

        int[] dec = new int[n]; // Длина убывающего начала подмассива

                                // по всем показателям

        int max;

  

        // Длина возрастающей последовательности, заканчивающейся первым индексом, равна 1

        inc[0] = 1;

  

        // Длина возрастающей последовательности, начиная с первого индекса, равна 1

        dec[n-1] = 1;

  

        // Шаг 1) Построить растущий массив последовательностей

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

           inc[i] = (arr[i] >= arr[i-1])? inc[i-1] + 1: 1;

  

        // Шаг 2) Построить убывающий массив последовательностей

        for (int i = n-2; i >= 0; i--)

            dec[i] = (arr[i] >= arr[i+1])? dec[i+1] + 1: 1;

  

        // Шаг 3) Найти длину максимальной битовой последовательности

        max = inc[0] + dec[0] - 1;

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

            if (inc[i] + dec[i] - 1 > max)

                max = inc[i] + dec[i] - 1;

  

        return max;

    }

  

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

    public static void main (String[] args)

    {

        int arr[] = {12, 4, 78, 90, 45, 23};

        int n = arr.length;

        System.out.println("Length of max length Bitnoic Subarray is "

                            + bitonic(arr, n));

    }

}
/ * Этот код предоставлен Девешом Агравалом * /

питон

# Программа Python для определения длины самого длинного битонного подмассива

  

def bitonic(arr, n):

      

    # Длина увеличивающегося окончания подмассива по всем индексам

    inc = [None] *

      

    # Длина убывающего подмассива, начиная со всех индексов

    dec = [None] * n

      

    # длина возрастающей последовательности, заканчивающейся в первом индексе, равна 1

    inc[0] = 1

      

    # длина возрастающей последовательности, начиная с первого индекса, равна 1

    dec[n-1] = 1

  

    # Шаг 1) Построить увеличивающийся массив последовательностей

    for i in range(n):

        if arr[i] >= arr[i-1]:

            inc[i] = inc[i-1] + 1

        else:

            inc[i] = 1

  

    # Шаг 2) Построить убывающий массив последовательностей

    for i in range(n-2,-1,-1):

        if arr[i] >= arr[i-1]:

            dec[i] = inc[i-1] + 1

        else:

            dec[i] = 1

  

    # Шаг 3) Найдите длину максимальной битовой последовательности

    max = inc[0] + dec[0] - 1

    for i in range(n):

        if inc[i] + dec[i] - 1 > max:

            max = inc[i] + dec[i] - 1

  

    return max

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

  

arr = [12, 4, 78, 90, 45, 23]

n = len(arr)

print("nLength of max length Bitnoic Subarray is ",bitonic(arr, n))

C #

// C # программа для определения длины
// самый длинный битонный подмассив

using System;

  

class GFG

{

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

    {

        // Длина возрастающего окончания подмассива

        // по всем показателям

        int[] inc = new int[n]; 

          

        // Длина убывающего начала подмассива

        // по всем показателям

        int[] dec = new int[n]; 

          

        int max;

  

        // Длина возрастающей последовательности

        // конец первого индекса равен 1

        inc[0] = 1;

  

        // Длина возрастающей последовательности

        // начиная с первого индекса 1

        dec[n - 1] = 1;

  

        // Шаг 1) Построить растущий массив последовательностей

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

        inc[i] = (arr[i] >= arr[i - 1]) ? 

                 inc[i - 1] + 1: 1;

  

        // Шаг 2) Построить убывающий массив последовательностей

        for (int i = n - 2; i >= 0; i--)

            dec[i] = (arr[i] >= arr[i + 1]) ? 

                     dec[i + 1] + 1: 1;

  

        // Шаг 3) Найти длину максимума

        // длина битовой последовательности

        max = inc[0] + dec[0] - 1;

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

            if (inc[i] + dec[i] - 1 > max)

                max = inc[i] + dec[i] - 1;

  

        return max;

    }

  

    // Функция драйвера

    public static void Main ()

    {

        int []arr = {12, 4, 78, 90, 45, 23};

        int n = arr.Length;

        Console.Write("Length of max length Bitnoic Subarray is "

                      + bitonic(arr, n));

    }

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

PHP

<?php
// PHP программа для определения длины
// самый длинный битонный подмассив

  

function bitonic($arr, $n)

{

    $i; $max;

    // длина возрастающей последовательности

    // конец первого индекса равен 1

    $inc[0] = 1;

  

    // длина возрастающей последовательности

    // начиная с первого индекса 1

    $dec[$n - 1] = 1;

  

    // Шаг 1) Построить увеличение

    // массив последовательностей

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

    $inc[$i] = ($arr[$i] >= $arr[$i - 1]) ? 

                          $inc[$i - 1] + 1: 1;

  

    // Шаг 2) Построить убывающий

    // массив последовательностей

    for ($i = $n - 2; $i >= 0; $i--)

    $dec[$i] = ($arr[$i] >= $arr[$i + 1]) ? 

                          $dec[$i + 1] + 1: 1;

  

    // Шаг 3) Найти длину

    // максимальная длина битовой последовательности

    $max = $inc[0] + $dec[0] - 1;

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

        if ($inc[$i] + $dec[$i] - 1 > $max)

            $max = $inc[$i] + $dec[$i] - 1;

  

    return $max;

}

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

$arr = array(12, 4, 78, 90, 45, 23);

$n = sizeof($arr);

echo "Length of max length Bitnoic "

     "Subarray is ", bitonic($arr, $n);

      
// Этот код предоставлен aj_36
?>


Выход :

Length of max length Bitnoic Subarray is 5

Сложность времени: O (n)
Вспомогательное пространство: O (n)

Максимальная длина битонного субмассива | Установите 2 (O (n) время и O (1) пробел)

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

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

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

Максимальная длина битонного субмассива | Установите 1 (O (n) время и O (n) пространство)

0.00 (0%) 0 votes