Dada una array arr[] de longitud N . La tarea es encontrar la longitud del subarreglo más largo en el que los elementos mayores que un número dado K son más que los elementos que no son mayores que K.
Ejemplos:
Entrada: N = 5, K = 2, arr[]={ 1, 2, 3, 4, 1 }
Salida: 3
El subarreglo [2, 3, 4] o [3, 4, 1] satisface la condición dada, y no hay subarreglo de
longitud 4 o 5 que cumpla la condición dada, por lo que la respuesta es 3.Entrada: N = 4, K = 2, arr[]={ 6, 5, 3, 4 }
Salida: 4
Acercarse:
- La idea es utilizar el concepto de búsqueda binaria sobre la suma parcial.
- Primero, reemplace los elementos que son mayores que K por 1 y otros elementos por -1 y calcule la suma del prefijo sobre él. Ahora bien, si un subarreglo tiene una suma mayor que 0 , implica que contiene más elementos mayores que K que elementos que son menores que K.
- Para encontrar la respuesta, utilice la búsqueda binaria sobre la respuesta. En cada paso de la búsqueda binaria, verifique cada subarreglo de esa longitud y luego decida si busca una longitud mayor o no.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// C++ implementation of above approach
// Function to find the length of a
// longest subarray in which elements
// greater than K are more than
// elements not greater than K
int LongestSubarray(int a[], int n, int k)
{
int pre[n] = { 0 };
// Create a new array in which we store 1
// if a[i] > k otherwise we store -1.
for (int i = 0; i < n; i++) {
if (a[i] > k)
pre[i] = 1;
else
pre[i] = -1;
}
// Taking prefix sum over it
for (int i = 1; i < n; i++)
pre[i] = pre[i - 1] + pre[i];
// len will store maximum
// length of subarray
int len = 0;
int lo = 1, hi = n;
while (lo <= hi) {
int mid = (lo + hi) / 2;
// This indicate there is at least one
// subarray of length mid that has sum > 0
bool ok = false;
// Check every subarray of length mid if
// it has sum > 0 or not if sum > 0 then it
// will satisfy our required condition
for (int i = mid - 1; i < n; i++) {
// x will store the sum of
// subarray of length mid
int x = pre[i];
if (i - mid >= 0)
x -= pre[i - mid];
// Satisfy our given condition
if (x > 0) {
ok = true;
break;
}
}
// Check for higher length as we
// get length mid
if (ok == true) {
len = mid;
lo = mid + 1;
}
// Check for lower length as we
// did not get length mid
else
hi = mid - 1;
}
return len;
}
// Driver code
int main()
{
int a[] = { 2, 3, 4, 5, 3, 7 };
int k = 3;
int n = sizeof(a) / sizeof(a[0]);
cout << LongestSubarray(a, n, k);
return 0;
}
Java
// Java implementation of above approach
class GFG
{
// Function to find the length of a
// longest subarray in which elements
// greater than K are more than
// elements not greater than K
static int LongestSubarray(int a[], int n, int k)
{
int []pre = new int[n];
// Create a new array in which we store 1
// if a[i] > k otherwise we store -1.
for (int i = 0; i < n; i++)
{
if (a[i] > k)
pre[i] = 1;
else
pre[i] = -1;
}
// Taking prefix sum over it
for (int i = 1; i < n; i++)
pre[i] = pre[i - 1] + pre[i];
// len will store maximum
// length of subarray
int len = 0;
int lo = 1, hi = n;
while (lo <= hi)
{
int mid = (lo + hi) / 2;
// This indicate there is at least one
// subarray of length mid that has sum > 0
boolean ok = false;
// Check every subarray of length mid if
// it has sum > 0 or not if sum > 0 then it
// will satisfy our required condition
for (int i = mid - 1; i < n; i++)
{
// x will store the sum of
// subarray of length mid
int x = pre[i];
if (i - mid >= 0)
x -= pre[i - mid];
// Satisfy our given condition
if (x > 0)
{
ok = true;
break;
}
}
// Check for higher length as we
// get length mid
if (ok == true)
{
len = mid;
lo = mid + 1;
}
// Check for lower length as we
// did not get length mid
else
hi = mid - 1;
}
return len;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 2, 3, 4, 5, 3, 7 };
int k = 3;
int n = a.length;
System.out.println(LongestSubarray(a, n, k));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of above approach # Function to find the Length of a # longest subarray in which elements # greater than K are more than # elements not greater than K def LongestSubarray(a, n, k): pre = [0 for i in range(n)] # Create a new array in which we store 1 # if a[i] > k otherwise we store -1. for i in range(n): if (a[i] > k): pre[i] = 1 else: pre[i] = -1 # Taking prefix sum over it for i in range(1, n): pre[i] = pre[i - 1] + pre[i] # Len will store maximum # Length of subarray Len = 0 lo = 1 hi = n while (lo <= hi): mid = (lo + hi) // 2 # This indicate there is at least one # subarray of Length mid that has sum > 0 ok = False # Check every subarray of Length mid if # it has sum > 0 or not if sum > 0 then it # will satisfy our required condition for i in range(mid - 1, n): # x will store the sum of # subarray of Length mid x = pre[i] if (i - mid >= 0): x -= pre[i - mid] # Satisfy our given condition if (x > 0): ok = True break # Check for higher Length as we # get Length mid if (ok == True): Len = mid lo = mid + 1 # Check for lower Length as we # did not get Length mid else: hi = mid - 1 return Len # Driver code a = [2, 3, 4, 5, 3, 7] k = 3 n = len(a) print(LongestSubarray(a, n, k)) # This code is contributed by Mohit Kumar
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to find the length of a
// longest subarray in which elements
// greater than K are more than
// elements not greater than K
static int LongestSubarray(int[] a, int n, int k)
{
int []pre = new int[n];
// Create a new array in which we store 1
// if a[i] > k otherwise we store -1.
for (int i = 0; i < n; i++)
{
if (a[i] > k)
pre[i] = 1;
else
pre[i] = -1;
}
// Taking prefix sum over it
for (int i = 1; i < n; i++)
pre[i] = pre[i - 1] + pre[i];
// len will store maximum
// length of subarray
int len = 0;
int lo = 1, hi = n;
while (lo <= hi)
{
int mid = (lo + hi) / 2;
// This indicate there is at least one
// subarray of length mid that has sum > 0
bool ok = false;
// Check every subarray of length mid if
// it has sum > 0 or not if sum > 0 then it
// will satisfy our required condition
for (int i = mid - 1; i < n; i++)
{
// x will store the sum of
// subarray of length mid
int x = pre[i];
if (i - mid >= 0)
x -= pre[i - mid];
// Satisfy our given condition
if (x > 0)
{
ok = true;
break;
}
}
// Check for higher length as we
// get length mid
if (ok == true)
{
len = mid;
lo = mid + 1;
}
// Check for lower length as we
// did not get length mid
else
hi = mid - 1;
}
return len;
}
// Driver code
public static void Main()
{
int[] a = { 2, 3, 4, 5, 3, 7 };
int k = 3;
int n = a.Length;
Console.WriteLine(LongestSubarray(a, n, k));
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// javascript implementation of above approach
// Function to find the length of a
// longest subarray in which elements
// greater than K are more than
// elements not greater than K
function LongestSubarray(a , n , k)
{
var pre = Array.from({length: n}, (_, i) => 0);
// Create a new array in which we store 1
// if a[i] > k otherwise we store -1.
for (i = 0; i < n; i++)
{
if (a[i] > k)
pre[i] = 1;
else
pre[i] = -1;
}
// Taking prefix sum over it
for (i = 1; i < n; i++)
pre[i] = pre[i - 1] + pre[i];
// len will store maximum
// length of subarray
var len = 0;
var lo = 1, hi = n;
while (lo <= hi)
{
var mid = parseInt((lo + hi) / 2);
// This indicate there is at least one
// subarray of length mid that has sum > 0
var ok = false;
// Check every subarray of length mid if
// it has sum > 0 or not if sum > 0 then it
// will satisfy our required condition
for (i = mid - 1; i < n; i++)
{
// x will store the sum of
// subarray of length mid
var x = pre[i];
if (i - mid >= 0)
x -= pre[i - mid];
// Satisfy our given condition
if (x > 0)
{
ok = true;
break;
}
}
// Check for higher length as we
// get length mid
if (ok == true)
{
len = mid;
lo = mid + 1;
}
// Check for lower length as we
// did not get length mid
else
hi = mid - 1;
}
return len;
}
// Driver code
var a = [ 2, 3, 4, 5, 3, 7 ];
var k = 3;
var n = a.length;
document.write(LongestSubarray(a, n, k));
// This code is contributed by shikhasingrajput
</script>
Producción:
5
Complejidad de tiempo: O(N*logN)
Espacio auxiliar: O(N)