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

01.01.2020Массивы

Для данного массива 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] * n

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

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