Dado un arreglo de N enteros y un número K, la tarea es encontrar la longitud del subarreglo más largo en el que todos los elementos son mayores que K.
Ejemplos:
Entrada : a[] = {3, 4, 5, 6, 7, 2, 10, 11}, K = 5
Salida : 2
Hay dos subarreglos más largos posibles de longitud 2.
Son {6, 7} y {10 , 11}.
Entrada : a[] = {8, 25, 10, 19, 19, 18, 20, 11, 18}, K = 13
Salida : 4
El subarreglo más largo es {19, 19, 18, 20}.
La idea es comenzar a recorrer la array usando un contador. Si el elemento actual es mayor que el valor dado X, incremente el contador; de lo contrario, reemplace la longitud anterior con el máximo de la longitud anterior y el contador actual y reinicie el contador.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to print the length of the longest
// subarray with all elements greater than X
#include <bits/stdc++.h>
using namespace std;
// Function to count number of segments
int longestSubarray(int a[], int n, int x)
{
int count = 0;
int length = 0;
// Iterate in the array
for (int i = 0; i < n; i++) {
// check if array element
// greater than X or not
if (a[i] > x) {
count += 1;
}
else {
length = max(length, count);
count = 0;
}
}
// After iteration complete
// check for the last segment
if (count)
length = max(length, count);
return length;
}
// Driver Code
int main()
{
int a[] = { 8, 25, 10, 19, 19, 18, 20, 11, 18 };
int n = sizeof(a) / sizeof(a[0]);
int k = 13;
cout << longestSubarray(a, n, k);
return 0;
}
Java
// Java program to print the length of the longest
// subarray with all elements greater than X
import java.io.*;
class GFG {
// Function to count number of segments
static int longestSubarray(int a[], int n, int x)
{
int count = 0;
int length = 0;
// Iterate in the array
for (int i = 0; i < n; i++) {
// check if array element
// greater than X or not
if (a[i] > x) {
count += 1;
}
else {
length = Math.max(length, count);
count = 0;
}
}
// After iteration complete
// check for the last segment
if (count>0)
length = Math.max(length, count);
return length;
}
// Driver Code
public static void main (String[] args) {
int []a = { 8, 25, 10, 19, 19, 18, 20, 11, 18 };
int n = a.length;
int k = 13;
System.out.println(longestSubarray(a, n, k));
}
}
// This Code is contributed
// by shs
Python3
# Python3 program to print the length of # the longest subarray with all elements # greater than X # Function to count number of segments def longestSubarray(a, n, x): count = 0 length = 0 # Iterate in the array for i in range(n): # check if array element greater # than X or not if (a[i] > x): count += 1 else: length = max(length, count) count = 0 # After iteration complete # check for the last segment if (count > 0): length = max(length, count) return length # Driver Code if __name__ == '__main__': a = [ 8, 25, 10, 19, 19, 18, 20, 11, 18 ] n = len(a) k = 13 print(longestSubarray(a, n, k)) # This code is contributed by 29AjayKumar
C#
// C# program to print the length of the longest
// subarray with all elements greater than X
using System;
class GFG {
// Function to count number of segments
static int longestSubarray(int []a, int n, int x)
{
int count = 0;
int length = 0;
// Iterate in the array
for (int i = 0; i < n; i++) {
// check if array element
// greater than X or not
if (a[i] > x) {
count += 1;
}
else {
length = Math.Max(length, count);
count = 0;
}
}
// After iteration complete
// check for the last segment
if (count>0)
length = Math.Max(length, count);
return length;
}
// Driver Code
public static void Main () {
int []a = { 8, 25, 10, 19, 19, 18, 20, 11, 18 };
int n = a.Length;
int k = 13;
Console.WriteLine(longestSubarray(a, n, k));
}
}
// This Code is contributed
// by shs
PHP
<?php
// PHP program to print the length
// of the longest subarray with all
// elements greater than X
// Function to count number of segments
function longestSubarray($a, $n, $x)
{
$count = 0;
$length = 0;
// Iterate in the array
for ($i = 0; $i < $n; $i++)
{
// check if array element
// greater than X or not
if ($a[$i] > $x)
{
$count += 1;
}
else
{
$length = max($length, $count);
$count = 0;
}
}
// After iteration complete
// check for the last segment
if ($count > 0)
$length = max($length, $count);
return $length;
}
// Driver Code
$a = array( 8, 25, 10, 19, 19,
18, 20, 11, 18 );
$n = 9;
$k = 13;
echo longestSubarray($a, $n, $k);
// This code is contributed
// by Arnab Kundu
?>
Javascript
<script>
// javascript program to print the length of the longest
// subarray with all elements greater than X
// Function to count number of segments
function longestSubarray(a , n , x) {
var count = 0;
var length = 0;
// Iterate in the array
for (i = 0; i < n; i++) {
// check if array element
// greater than X or not
if (a[i] > x) {
count += 1;
} else {
length = Math.max(length, count);
count = 0;
}
}
// After iteration complete
// check for the last segment
if (count > 0)
length = Math.max(length, count);
return length;
}
// Driver Code
var a = [ 8, 25, 10, 19, 19, 18, 20, 11, 18 ];
var n = a.length;
var k = 13;
document.write(longestSubarray(a, n, k));
// This code is contributed by todaysgaurav
</script>
Producción:
4
Complejidad temporal : O(N)
Espacio auxiliar: O(1)