Dado un arreglo de enteros y un valor k, encuentre la longitud del subarreglo más grande que tenga una suma mayor que k.
Ejemplos:
Input : arr[] = {-2, 1, 6, -3}, k = 5
Output : 2
Largest subarray with sum greater than
5 is {1, 6}.
Input : arr[] = {2, -3, 3, 2, 0, -1}, k = 3
Output : 5
Largest subarray with sum greater than
3 is {2, -3, 3, 2, 0}.
Una solución simple es considerar uno por uno cada subarreglo y encontrar su suma. Si la suma es mayor que k, compare la longitud de este subarreglo con la longitud máxima encontrada hasta el momento. La complejidad temporal de esta solución es O(n 2 ).
un eficienteLa solución es usar la suma de prefijos y la búsqueda binaria. La idea es atravesar la array y almacenar la suma de prefijos y el índice de array correspondiente en un vector de pares. Después de encontrar la suma de prefijos, ordene el vector en orden creciente de suma de prefijos, y para el mismo valor de suma de prefijos, ordene según el índice. Cree otra array minInd[], en la que minInd[i] almacene el valor de índice mínimo en el rango [0..i] en el vector de suma de prefijos ordenados. Después de esto, comience a recorrer el arreglo arr[] y almacene la suma del subarreglo arr[0..i] en suma. Si la suma es mayor que k, entonces el subarreglo más grande que tiene una suma mayor que k es arr[0..i] con una longitud i + 1. Si la suma es menor o igual que k, entonces un valor mayor o igual a k + 1: se debe agregar suma a suma para que sea al menos k + 1. Sea este valor x. Para sumar x a sum, se puede restar -x porque sum-(-x) = sum + x. Por lo tanto, se necesita encontrar una array de prefijos arr[0..j] (j<i), que tenga suma como máximo -x (como máximo -x porque k+1-sum es el valor mínimo, ahora se toma su negativo, por lo que será el valor máximo permitido). El subarreglo resultante arr[j+1..i] debe ser lo más grande posible. Para ello, el valor de j debe ser el mínimo posible. Por lo tanto, el problema se reduce a encontrar una suma de prefijos que tenga como máximo el valor -x y su índice final sea mínimo. Para encontrar la suma de prefijos, se puede realizar una búsqueda binaria en el vector de suma de prefijos. Deje que el índice ind denote que en el vector de suma de prefijos todos los valores de suma de prefijos hasta el índice ind son menores o iguales a -x. El valor de índice mínimo en range[0..ind] es minInd[ind]. Si minInd[ind] es mayor que i, entonces no existe ningún subarreglo que tenga sum -x en range[0..i-1]. De lo contrario, arr[minInd[ind]+1..i] tiene una suma mayor que k.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find largest subarray
// having sum greater than k.
#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 largest subarray having sum
// greater than or equal to k.
int largestSub(int arr[], int n, int k)
{
int i;
// Length of largest 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 k, then answer
// is i+1.
if (sum > k)
maxlen = i + 1;
// If the sum is less than or equal to k, then
// find if there is a prefix array having sum
// that needs to be added to the current sum to
// make its value greater than k. If yes, then
// compare the length of updated subarray with
// maximum length found so far.
else {
int ind = findInd(preSum, n, sum - k - 1);
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 k = 5;
cout << largestSub(arr, n, k);
return 0;
}
Java
// Java program to find largest subarray
// having sum greater than k.
import java.util.*;
// defining pair class
class pair {
public int first;
public int second;
pair(int a, int b)
{
this.first = a;
this.second = b;
}
}
// implementing compare method
// to sort an array of pairs
class pairSort implements Comparator<pair> {
public int compare(pair a, pair b)
{
if (a.first == b.first)
return a.second - b.second;
return a.first - b.first;
}
}
class GFG {
// Function to find index in preSum vector upto which
// all prefix sum values are less than or equal to val.
static int findInd(pair[] 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 largest subarray having sum
// greater than or equal to k.
static int largestSub(int arr[], int n, int k)
{
int i;
// Length of largest subarray.
int maxlen = 0;
// Vector to store pair of prefix sum
// and corresponding ending index value.
pair[] preSum = new pair[n];
// To store current value of prefix sum.
int sum = 0;
// To store minimum index value in range
// 0..i of preSum vector.
int[] minInd = new int[n];
// Insert values in preSum vector.
for (i = 0; i < n; i++) {
sum = sum + arr[i];
preSum[i] = new pair(sum, i);
}
Arrays.sort(preSum, new pairSort());
// Update minInd array.
minInd[0] = preSum[0].second;
for (i = 1; i < n; i++) {
minInd[i]
= Math.min(minInd[i - 1], preSum[i].second);
}
sum = 0;
for (i = 0; i < n; i++) {
sum = sum + arr[i];
// If sum is greater than k, then answer
// is i+1.
if (sum > k)
maxlen = i + 1;
// If the sum is less than or equal to k, then
// find if there is a prefix array having sum
// that needs to be added to the current sum to
// make its value greater than k. If yes, then
// compare the length of updated subarray with
// maximum length found so far.
else {
int ind = findInd(preSum, n, sum - k - 1);
if (ind != -1 && minInd[ind] < i)
maxlen
= Math.max(maxlen, i - minInd[ind]);
}
}
return maxlen;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { -2, 1, 6, -3 };
int n = arr.length;
int k = 5;
// Function call
System.out.println(largestSub(arr, n, k));
}
}
// This code is contributed by phasing17
Python3
# Python3 program to find largest subarray # having sum greater than k. # Comparison function used to # sort preSum vector. def compare(a, b): if a[0] == b[0]: return a[1] < b[1] return a[0] < b[0] # Function to find index in preSum vector # 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, h = 0, 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 largest subarray having # sum greater than or equal to k. def largestSub(arr, n, k): # Length of largest subarray. maxlen = 0 # Vector to store pair of prefix sum # and corresponding ending index value. preSum = [] # To store the current value of prefix sum. Sum = 0 # To store minimum index value in range # 0..i of preSum vector. minInd = [None] * (n) # Insert values in preSum vector. for i in range(0, n): Sum = Sum + arr[i] preSum.append([Sum, i]) preSum.sort() # Update minInd array. minInd[0] = preSum[0][1] for i in range(1, n): minInd[i] = min(minInd[i - 1], preSum[i][1]) Sum = 0 for i in range(0, n): Sum = Sum + arr[i] # If sum is greater than k, then # answer is i+1. if Sum > k: maxlen = i + 1 # If sum is less than or equal to k, # then find if there is a prefix array # having sum that needs to be added to # current sum to make its value greater # than k. If yes, then compare length # of updated subarray with maximum # length found so far. else: ind = findInd(preSum, n, Sum - k - 1) if ind != -1 and minInd[ind] < i: maxlen = max(maxlen, i - minInd[ind]) return maxlen # Driver code. if __name__ == "__main__": arr = [-2, 1, 6, -3] n = len(arr) k = 5 print(largestSub(arr, n, k)) # This code is contributed # by Rituraj Jain
C#
// C# program to find largest subarray
// having sum greater than k.
using System;
using System.Collections.Generic;
// defining pair class
class pair {
public int first;
public int second;
public pair(int a, int b)
{
this.first = a;
this.second = b;
}
}
// implementing compare method
// to sort an array of pairs
class pairSort : Comparer<pair> {
public override int Compare(pair a, pair b)
{
if (a.first == b.first)
return a.second - b.second;
return a.first - b.first;
}
}
class GFG {
// Function to find index in preSum vector upto which
// all prefix sum values are less than or equal to val.
static int findInd(pair[] 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 largest subarray having sum
// greater than or equal to k.
static int largestSub(int[] arr, int n, int k)
{
int i;
// Length of largest subarray.
int maxlen = 0;
// Vector to store pair of prefix sum
// and corresponding ending index value.
pair[] preSum = new pair[n];
// To store current value of prefix sum.
int sum = 0;
// To store minimum index value in range
// 0..i of preSum vector.
int[] minInd = new int[n];
// Insert values in preSum vector.
for (i = 0; i < n; i++) {
sum = sum + arr[i];
preSum[i] = new pair(sum, i);
}
Array.Sort(preSum, new pairSort());
// Update minInd array.
minInd[0] = preSum[0].second;
for (i = 1; i < n; i++) {
minInd[i]
= Math.Min(minInd[i - 1], preSum[i].second);
}
sum = 0;
for (i = 0; i < n; i++) {
sum = sum + arr[i];
// If sum is greater than k, then answer
// is i+1.
if (sum > k)
maxlen = i + 1;
// If the sum is less than or equal to k, then
// find if there is a prefix array having sum
// that needs to be added to the current sum to
// make its value greater than k. If yes, then
// compare the length of updated subarray with
// maximum length found so far.
else {
int ind = findInd(preSum, n, sum - k - 1);
if (ind != -1 && minInd[ind] < i)
maxlen
= Math.Max(maxlen, i - minInd[ind]);
}
}
return maxlen;
}
// Driver code
public static void Main(string[] args)
{
int[] arr = { -2, 1, 6, -3 };
int n = arr.Length;
int k = 5;
// Function call
Console.WriteLine(largestSub(arr, n, k));
}
}
// This code is contributed by phasing17
Javascript
<script>
// JavaScript program to find largest subarray
// having sum greater than k.
// Comparison function used to
// sort preSum vector.
function compare(a, b){
if(a[0] == b[0])
return a[1] < b[1]
return a[0] < b[0]
}
// Function to find index in preSum vector
// 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){
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 largest subarray having
// sum greater than or equal to k.
function largestSub(arr, n, k){
// Length of largest subarray.
let maxlen = 0
// Vector to store pair of prefix sum
// and corresponding ending index value.
let preSum = []
// To store the current value of prefix sum.
let Sum = 0
// To store minimum index value in range
// 0..i of preSum vector.
let minInd = new Array(n)
// Insert values in preSum vector.
for(let i = 0; i < n; i++){
Sum = Sum + arr[i]
preSum.push([Sum, i])
}
preSum.sort(compare)
// 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])
}
Sum = 0
for(let i = 0; i < n; i++)
{
Sum = Sum + arr[i]
// If sum is greater than k, then
// answer is i+1.
if(Sum > k)
maxlen = i + 1
// If sum is less than or equal to k,
// then find if there is a prefix array
// having sum that needs to be added to
// current sum to make its value greater
// than k. If yes, then compare length
// of updated subarray with maximum
// length found so far.
else{
ind = findInd(preSum, n, Sum - k - 1)
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 k = 5
document.write(largestSub(arr, n, k))
// This code is contributed by shinjanpatra
</script>
Producción:
2
Complejidad temporal: O(nlogn)
Espacio auxiliar: O(n)