Dado un arreglo de enteros distintos, encuentre la longitud del subarreglo más largo que contiene números que se pueden ordenar en una secuencia continua.
Ejemplos:
C++
#include<iostream>
using namespace std;
// Utility functions to find minimum and maximum of
// two elements
int min(int x, int y) { return (x < y)? x : y; }
int max(int x, int y) { return (x > y)? x : y; }
// Returns length of the longest contiguous subarray
int findLength(int arr[], int n)
{
int max_len = 1; // Initialize result
for (int i=0; i<n-1; i++)
{
// Initialize min and max for all subarrays starting with i
int mn = arr[i], mx = arr[i];
// Consider all subarrays starting with i and ending with j
for (int j=i+1; j<n; j++)
{
// Update min and max in this subarray if needed
mn = min(mn, arr[j]);
mx = max(mx, arr[j]);
// If current subarray has all contiguous elements
if ((mx - mn) == j-i)
max_len = max(max_len, mx-mn+1);
}
}
return max_len; // Return result
}
// Driver program to test above function
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;
}
Java
class LargestSubArray2
{
// Utility functions to find minimum and maximum of
// two elements
int min(int x, int y)
{
return (x < y) ? x : y;
}
int max(int x, int y)
{
return (x > y) ? x : y;
}
// Returns length of the longest contiguous subarray
int findLength(int arr[], int n)
{
int max_len = 1; // Initialize result
for (int i = 0; i < n - 1; i++)
{
// Initialize min and max for all subarrays starting with i
int mn = arr[i], mx = arr[i];
// Consider all subarrays starting with i and ending with j
for (int j = i + 1; j < n; j++)
{
// Update min and max in this subarray if needed
mn = min(mn, arr[j]);
mx = max(mx, arr[j]);
// If current subarray has all contiguous elements
if ((mx - mn) == j - i)
max_len = max(max_len, mx - mn + 1);
}
}
return max_len; // Return result
}
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));
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# Python3 program to find length
# of the longest subarray
# Utility functions to find minimum
# and maximum of two elements
def min(x, y):
return x if(x < y) else y
def max(x, y):
return x if(x > y) else y
# Returns length of the longest
# contiguous subarray
def findLength(arr, n):
# Initialize result
max_len = 1
for i in range(n - 1):
# Initialize min and max for
# all subarrays starting with i
mn = arr[i]
mx = arr[i]
# Consider all subarrays starting
# with i and ending with j
for j in range(i + 1, n):
# Update min and max in
# this subarray if needed
mn = min(mn, arr[j])
mx = max(mx, arr[j])
# If current subarray has
# all contiguous elements
if ((mx - mn) == j - i):
max_len = max(max_len, mx - mn + 1)
return max_len
# Driver Code
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))
# This code is contributed by Anant Agarwal.
C#
using System;
class GFG {
// Returns length of the longest
// contiguous subarray
static int findLength(int []arr, int n)
{
int max_len = 1; // Initialize result
for (int i = 0; i < n - 1; i++)
{
// Initialize min and max for all
// subarrays starting with i
int mn = arr[i], mx = arr[i];
// Consider all subarrays starting
// with i and ending with j
for (int j = i + 1; j < n; j++)
{
// Update min and max in this
// subarray if needed
mn = Math.Min(mn, arr[j]);
mx = Math.Max(mx, arr[j]);
// If current subarray has all
// contiguous elements
if ((mx - mn) == j - i)
max_len = Math.Max(max_len,
mx - mn + 1);
}
}
return max_len; // Return result
}
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));
}
}
// This code is contributed by Sam007.
PHP
<?php
// Utility functions to find minimum
// and maximum of two elements
function mins($x, $y)
{
if($x < $y)
return $x;
else
return $y;
}
function maxi($a, $b)
{
if($a > $b)
return $a;
else
return $b;
}
// Returns length of the longest
// contiguous subarray
function findLength(&$arr, $n)
{
$max_len = 1; // Initialize result
for ($i = 0; $i < $n - 1; $i++)
{
// Initialize min and max for all
// subarrays starting with i
$mn = $arr[$i];
$mx = $arr[$i];
// Consider all subarrays starting
// with i and ending with j
for ($j = $i + 1; $j < $n; $j++)
{
// Update min and max in this
// subarray if needed
$mn = mins($mn, $arr[$j]);
$mx = maxi($mx, $arr[$j]);
// If current subarray has all
// contiguous elements
if (($mx - $mn) == $j - $i)
$max_len = maxi($max_len,
$mx - $mn + 1);
}
}
return $max_len; // Return result
}
// Driver Code
$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));
// This code is contributed
// by Shivi_Aggarwal.
?>
Javascript
<script>
// Utility functions to find minimum
// and maximum of two elements
function min( x, y) { return (x < y)? x : y; }
function max( x, y) { return (x > y)? x : y; }
// Returns length of the longest
// contiguous subarray
function findLength( arr, n)
{
let max_len = 1; // Initialize result
for (let i=0; i<n-1; i++)
{
// Initialize min and max for all
// subarrays starting with i
let mn = arr[i], mx = arr[i];
// Consider all subarrays starting
// with i and ending with j
for (let j=i+1; j<n; j++)
{
// Update min and max in this
// subarray if needed
mn = min(mn, arr[j]);
mx = max(mx, arr[j]);
// If current subarray has all
// contiguous elements
if ((mx - mn) == j-i)
max_len = Math.max(max_len, mx-mn+1);
}
}
return max_len; // Return result
}
// driver code
let arr = [1, 56, 58, 57, 90, 92, 94, 93, 91, 45];
let n = arr.length;
document.write("Length of the longest contiguous subarray is "
+ findLength(arr, n));
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA