Dada una array de enteros y un entero x. Encuentre la longitud del subarreglo de tamaño máximo que tiene un promedio de enteros mayores o iguales a x.
Ejemplos:
Input : arr[] = {-2, 1, 6, -3}, x = 3
Output : 2
Longest subarray is {1, 6} having average
3.5 greater than x = 3.
Input : arr[] = {2, -3, 3, 2, 1}, x = 2
Output : 3
Longest subarray is {3, 2, 1} having
average 2 equal to x = 2.
Una solución simple es considerar uno por uno cada subarreglo y encontrar su promedio. Si el promedio es mayor o igual a x, entonces compare la longitud del subarreglo con la longitud máxima encontrada hasta el momento. La complejidad temporal de esta solución es O(n 2 ).
Una solución eficiente es utilizar la búsqueda binaria y la suma de prefijos. Deje que el subarreglo más largo requerido sea arr[i..j] y su longitud sea l = j-i+1. Por lo tanto, matemáticamente se puede escribir como:
(Σ (arr[i..j]) / l ) ≥ x
==> (Σ (arr[i..j]) / l) – x ≥ 0
==> (Σ (arr[i..j] ) – x*l) / l ≥ 0 …(1)
La ecuación (1) es equivalente a restar x de cada elemento del subarreglo y luego sacar el promedio del subarreglo resultante. Entonces, el subarreglo resultante se puede obtener restando x de cada elemento del arreglo. Deje que el subarreglo actualizado sea arr1. La ecuación (1) se puede simplificar aún más como:
Σ (arr1[i..j]) / l ≥ 0
==> Σ (arr1[i..j]) ≥ 0 …(2)
La ecuación (2) es simplemente el subarreglo más largo que tiene una suma mayor o igual a cero. El subarreglo más largo que tiene una suma mayor o igual a cero se puede encontrar mediante el método que se analiza en el siguiente artículo:
el subarreglo más largo que tiene una suma mayor que k .
El algoritmo paso a paso es:
1. Reste x de cada elemento de la array.
2. Encuentre el subarreglo más largo que tenga una suma mayor o igual a cero en el arreglo actualizado usando la suma de prefijos y la búsqueda binaria.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find Longest subarray
// having average greater than or equal
// to x.
#include <bits/stdc++.h>
using namespace std;
// Comparison function used to sort preSum vector.
bool compare(const pair<int, int>& a, const pair<int, int>& b)
{
if (a.first == b.first)
return a.second < b.second;
return a.first < b.first;
}
// Function to find index in preSum vector upto which
// all prefix sum values are less than or equal to val.
int findInd(vector<pair<int, int> >& preSum, int n, int val)
{
// Starting and ending index of search space.
int l = 0;
int h = n - 1;
int mid;
// To store required index value.
int ans = -1;
// If middle value is less than or equal to
// val then index can lie in mid+1..n
// else it lies in 0..mid-1.
while (l <= h) {
mid = (l + h) / 2;
if (preSum[mid].first <= val) {
ans = mid;
l = mid + 1;
}
else
h = mid - 1;
}
return ans;
}
// Function to find Longest subarray having average
// greater than or equal to x.
int LongestSub(int arr[], int n, int x)
{
int i;
// Update array by subtracting x from
// each element.
for (i = 0; i < n; i++)
arr[i] -= x;
// Length of Longest subarray.
int maxlen = 0;
// Vector to store pair of prefix sum
// and corresponding ending index value.
vector<pair<int, int> > preSum;
// To store current value of prefix sum.
int sum = 0;
// To store minimum index value in range
// 0..i of preSum vector.
int minInd[n];
// Insert values in preSum vector.
for (i = 0; i < n; i++) {
sum = sum + arr[i];
preSum.push_back({ sum, i });
}
sort(preSum.begin(), preSum.end(), compare);
// Update minInd array.
minInd[0] = preSum[0].second;
for (i = 1; i < n; i++) {
minInd[i] = min(minInd[i - 1], preSum[i].second);
}
sum = 0;
for (i = 0; i < n; i++) {
sum = sum + arr[i];
// If sum is greater than or equal to 0,
// then answer is i+1.
if (sum >= 0)
maxlen = i + 1;
// If sum is less than 0, then find if
// there is a prefix array having sum
// that needs to be added to current sum to
// make its value greater than or equal to 0.
// If yes, then compare length of updated
// subarray with maximum length found so far.
else {
int ind = findInd(preSum, n, sum);
if (ind != -1 && minInd[ind] < i)
maxlen = max(maxlen, i - minInd[ind]);
}
}
return maxlen;
}
// Driver code.
int main()
{
int arr[] = { -2, 1, 6, -3 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 3;
cout << LongestSub(arr, n, x);
return 0;
}
Python3
# Python3 program to find longest subarray # having average greater than or equal to x # Function to find index in preSum list of # tuples upto which all prefix sum values # are less than or equal to val. def findInd(preSum, n, val): # Starting and ending index # of search space. l = 0 h = n - 1 # To store required index value ans = -1 # If middle value is less than or # equal to val then index can # lie in mid+1..n else it lies # in 0..mid-1 while (l <= h): mid = (l + h) // 2 if preSum[mid][0] <= val: ans = mid l = mid + 1 else: h = mid - 1 return ans # Function to find Longest subarray # having average greater than or # equal to x. def LongestSub(arr, n, x): # Update array by subtracting # x from each element for i in range(n): arr[i] -= x # Length of Longest subarray. maxlen = 0 # To store current value of # prefix sum. total = 0 # To store minimum index value in # range 0..i of preSum vector. minInd = [None] * n # list to store pair of prefix sum # and corresponding ending index value. preSum = [] # Insert values in preSum vector for i in range(n): total += arr[i] preSum.append((total, i)) preSum = sorted(preSum) # Update minInd array. minInd[0] = preSum[0][1] for i in range(1, n): minInd[i] = min(minInd[i - 1], preSum[i][1]) total = 0 for i in range(n): total += arr[i] # If sum is greater than or equal # to 0, then answer is i+1 if total >= 0: maxlen = i + 1 # If sum is less than 0, then find if # there is a prefix array having sum # that needs to be added to current sum to # make its value greater than or equal to 0. # If yes, then compare length of updated # subarray with maximum length found so far else: ind = findInd(preSum, n, total) if (ind != -1) & (minInd[ind] < i): maxlen = max(maxlen, i - minInd[ind]) return maxlen # Driver Code if __name__ == '__main__': arr = [ -2, 1, 6, -3 ] n = len(arr) x = 3 print(LongestSub(arr, n, x)) # This code is contributed by Vikas Chitturi
Javascript
<script>
// JavaScript program to find longest subarray
// having average greater than or equal to x
// Function to find index in preSum list of
// tuples upto which all prefix sum values
// are less than or equal to val.
function findInd(preSum, n, val)
{
// Starting and ending index
// of search space.
let l = 0
let h = n - 1
// To store required index value
let ans = -1
// If middle value is less than or
// equal to val then index can
// lie in mid+1..n else it lies
// in 0..mid-1
while (l <= h){
let mid = Math.floor((l + h)/2);
if(preSum[mid][0] <= val){
ans = mid
l = mid + 1
}
else{
h = mid - 1
}
}
return ans
}
// Function to find Longest subarray
// having average greater than or
// equal to x.
function LongestSub(arr, n, x)
{
// Update array by subtracting
// x from each element
for(let i = 0; i < n; i++)
{
arr[i] -= x
}
// Length of Longest subarray.
let maxlen = 0
// To store current value of
// prefix sum.
let total = 0
// To store minimum index value in
// range 0..i of preSum vector.
let minInd = new Array(n);
// list to store pair of prefix sum
// and corresponding ending index value.
let preSum = []
// Insert values in preSum vector
for(let i=0;i<n;i++){
total += arr[i];
preSum.push([total, i]);
}
preSum.sort();
// Update minInd array.
minInd[0] = preSum[0][1]
for(let i = 1; i < n; i++){
minInd[i] = Math.min(minInd[i - 1],
preSum[i][1]);
}
total = 0;
for(let i=0;i<n;i++){
total += arr[i];
// If sum is greater than or equal
// to 0, then answer is i+1
if(total >= 0){
maxlen = i + 1
}
// If sum is less than 0, then find if
// there is a prefix array having sum
// that needs to be added to current sum to
// make its value greater than or equal to 0.
// If yes, then compare length of updated
// subarray with maximum length found so far
else{
let ind = findInd(preSum, n, total)
if((ind != -1) && (minInd[ind] < i)){
maxlen = Math.max(maxlen, i - minInd[ind]);
}
}
}
return maxlen;
}
// Driver Code
let arr = [ -2, 1, 6, -3 ]
let n = arr.length
let x = 3
document.write(LongestSub(arr, n, x))
// This code is contributed by shinjanpatra
</script>
2
Complejidad temporal: O(nlogn)
Espacio auxiliar: O(n)