Dada una array de n números donde la diferencia entre cada número y el anterior no excede de uno. Encuentre el subarreglo contiguo más largo tal que la diferencia entre el número máximo y mínimo en el rango no exceda uno.
Ejemplos:
Input : {3, 3, 4, 4, 5, 6}
Output : 4
The longest subarray here is {3, 3, 4, 4}
Input : {7, 7, 7}
Output : 3
The longest subarray here is {7, 7, 7}
Input : {9, 8, 8, 9, 9, 10}
Output : 5
The longest subarray here is {9, 8, 8, 9, 9}
Si la diferencia entre los números máximo y mínimo en la secuencia no excede uno, entonces la secuencia consistía en solo uno o dos números consecutivos. La idea es recorrer la array y realizar un seguimiento del elemento actual y el elemento anterior en el subarreglo actual. Si encontramos un elemento que no es el mismo que el actual o el anterior, actualizamos el actual y el anterior. También actualizamos el resultado si es necesario.
C++
// C++ code to find longest
// subarray with difference
// between max and min as at-most 1.
#include<bits/stdc++.h>
using namespace std;
int longestSubarray(int input[],
int length)
{
int prev = -1;
int current, next;
int prevCount = 0, currentCount = 1;
// longest constant range length
int longest = 1;
// first number
current = input[0];
for (int i = 1; i < length; i++)
{
next = input[i];
// If we see same number
if (next == current)
{
currentCount++;
}
// If we see different number,
// but same as previous.
else if (next == prev)
{
prevCount += currentCount;
prev = current;
current = next;
currentCount = 1;
}
// If number is neither same
// as previous nor as current.
else
{
longest = max(longest,
currentCount + prevCount);
prev = current;
prevCount = currentCount;
current = next;
currentCount = 1;
}
}
return max(longest,
currentCount + prevCount);
}
// Driver Code
int main()
{
int input[] = { 5, 5, 6, 7, 6 };
int n = sizeof(input) / sizeof(int);
cout << longestSubarray(input, n);
return 0;
}
// This code is contributed
// by Arnab Kundu
Java
// Java code to find longest subarray with difference
// between max and min as at-most 1.
public class Demo {
public static int longestSubarray(int[] input)
{
int prev = -1;
int current, next;
int prevCount = 0, currentCount = 1;
// longest constant range length
int longest = 1;
// first number
current = input[0];
for (int i = 1; i < input.length; i++) {
next = input[i];
// If we see same number
if (next == current) {
currentCount++;
}
// If we see different number, but
// same as previous.
else if (next == prev) {
prevCount += currentCount;
prev = current;
current = next;
currentCount = 1;
}
// If number is neither same as previous
// nor as current.
else {
longest = Math.max(longest, currentCount + prevCount);
prev = current;
prevCount = currentCount;
current = next;
currentCount = 1;
}
}
return Math.max(longest, currentCount + prevCount);
}
public static void main(String[] args)
{
int[] input = { 5, 5, 6, 7, 6 };
System.out.println(longestSubarray(input));
}
}
Python 3
# Python 3 code to find longest # subarray with difference # between max and min as at-most 1. def longestSubarray(input, length): prev = -1 prevCount = 0 currentCount = 1 # longest constant range length longest = 1 # first number current = input[0] for i in range(1, length): next = input[i] # If we see same number if next == current : currentCount += 1 # If we see different number, # but same as previous. elif next == prev : prevCount += currentCount prev = current current = next currentCount = 1 # If number is neither same # as previous nor as current. else: longest = max(longest, currentCount + prevCount) prev = current prevCount = currentCount current = next currentCount = 1 return max(longest, currentCount + prevCount) # Driver Code if __name__ == "__main__": input = [ 5, 5, 6, 7, 6 ] n = len(input) print(longestSubarray(input, n)) # This code is contributed # by ChitraNayal
C#
// C# code to find longest
// subarray with difference
// between max and min as
// at-most 1.
using System;
class GFG
{
public static int longestSubarray(int[] input)
{
int prev = -1;
int current, next;
int prevCount = 0,
currentCount = 1;
// longest constant
// range length
int longest = 1;
// first number
current = input[0];
for (int i = 1;
i < input.Length; i++)
{
next = input[i];
// If we see same number
if (next == current)
{
currentCount++;
}
// If we see different number,
// but same as previous.
else if (next == prev)
{
prevCount += currentCount;
prev = current;
current = next;
currentCount = 1;
}
// If number is neither
// same as previous
// nor as current.
else
{
longest = Math.Max(longest,
currentCount +
prevCount);
prev = current;
prevCount = currentCount;
current = next;
currentCount = 1;
}
}
return Math.Max(longest,
currentCount + prevCount);
}
// Driver Code
public static void Main(String[] args)
{
int[] input = {5, 5, 6, 7, 6};
Console.WriteLine(longestSubarray(input));
}
}
// This code is contributed
// by Kirti_Mangal
PHP
<?php
// PHP code to find longest subarray
// with difference between max and
// min as at-most 1.
function longestSubarray($input, $length)
{
$prev = -1;
$prevCount = 0;
$currentCount = 1;
// longest constant range length
$longest = 1;
// first number
$current = $input[0];
for ($i = 1; $i < $length; $i++)
{
$next = $input[$i];
// If we see same number
if ($next == $current)
{
$currentCount++;
}
// If we see different number,
// but same as previous.
else if ($next == $prev)
{
$prevCount += $currentCount;
$prev = $current;
$current = $next;
$currentCount = 1;
}
// If number is neither same
// as previous nor as current.
else
{
$longest = max($longest,
$currentCount +
$prevCount);
$prev = $current;
$prevCount = $currentCount;
$current = $next;
$currentCount = 1;
}
}
return max($longest,
$currentCount + $prevCount);
}
// Driver Code
$input = array( 5, 5, 6, 7, 6 );
echo(longestSubarray($input, count($input)));
// This code is contributed
// by Arnab Kundu
?>
Javascript
<script>
// Javascript code to find longest
// subarray with difference
// between max and min as at-most 1.
function longestSubarray(input)
{
let prev = -1;
let current, next;
let prevCount = 0, currentCount = 1;
// longest constant range length
let longest = 1;
// first number
current = input[0];
for (let i = 1; i < input.length; i++) {
next = input[i];
// If we see same number
if (next == current) {
currentCount++;
}
// If we see different number, but
// same as previous.
else if (next == prev) {
prevCount += currentCount;
prev = current;
current = next;
currentCount = 1;
}
// If number is neither same as previous
// nor as current.
else {
longest = Math.max(longest,
currentCount + prevCount);
prev = current;
prevCount = currentCount;
current = next;
currentCount = 1;
}
}
return Math.max(longest,
currentCount + prevCount);
}
let input=[5, 5, 6, 7, 6];
document.write(longestSubarray(input));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
3
Complejidad de tiempo: O(n) donde n es la longitud de la array de entrada.
Publicación traducida automáticamente
Artículo escrito por salmayehia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA