Dada una array arr[] que consta de N enteros, la tarea es encontrar los índices inicial y final del primer subarreglo con una suma negativa. Imprima «-1» si no existe tal subarreglo.
Nota: En el caso de múltiples subarreglos de suma negativa en el arreglo dado, el primer subarreglo se refiere al subarreglo con el índice inicial más bajo.
Ejemplos:
Entrada: arr[] = {3, 3, -4, -2}
Salida: 1 2
Explicación:
El primer subarreglo con suma negativa es del índice 1 al 2 que es arr[1] + arr[2] = -1.Entrada: arr[] = {1, 2, 3, 10}.
Salida: -1
Explicación:
No existe ningún subarreglo con suma negativa.
Enfoque ingenuo: el enfoque ingenuo es generar todos los subarreglos de izquierda a derecha en el arreglo y verificar si alguno de estos subarreglos tiene una suma negativa o no. En caso afirmativo, imprima el índice inicial y final de ese subarreglo.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: la idea es resolver el problema utilizando Prefix Sum y Hashing . A continuación se muestran los pasos:
- Calcule la suma de prefijos de la array y guárdela en HashMap .
- Itere a través de la array y para cada i -ésimo índice, donde i oscila entre [0, N – 1] , verifique si el elemento en el i -ésimo índice es negativo o no. Si es así, entonces arr[i] es el subarreglo requerido.
- De lo contrario, busque un índice a partir de i + 1, donde la suma del prefijo sea menor que la suma del prefijo hasta i .
- Si se encuentra alguno de estos índices en el paso anterior, entonces el subarreglo de índices {i, índice} da el primer subarreglo negativo.
- Si no se encuentra tal subarreglo, imprima «-1» . De lo contrario, imprima el subarreglo obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if a sum less
// than pre_sum is present
int b_search(int pre_sum,
map<int, vector<int> >& m,
int index)
{
// Returns an iterator either equal
// to given key or next greater
auto it = m.lower_bound(pre_sum);
if (it == m.begin())
return -1;
// Decrement the iterator
it--;
// Check if the sum found at
// a greater index
auto it1
= lower_bound(it->second.begin(),
it->second.end(),
index);
if (*it1 > index)
return *it1;
return -1;
}
// Function to return the index
// of first negative subarray sum
vector<int> findSubarray(int arr[], int n)
{
// Stores the prefix sum- index
// mappings
map<int, vector<int> > m;
int sum = 0;
// Stores the prefix sum of
// the original array
int prefix_sum[n];
for (int i = 0; i < n; i++) {
sum += arr[i];
// Check if we get sum negative
// starting from first element
if (sum < 0)
return { 0, i };
prefix_sum[i] = sum;
m[sum].push_back(i);
}
// Iterate through array find
// the sum which is just less
// then the previous prefix sum
for (int i = 1; i < n; i++) {
// Check if the starting element
// is itself negative
if (arr[i] < 0)
// arr[i] becomes the required
// subarray
return { i, i };
else {
int pre_sum = prefix_sum[i - 1];
// Find the index which forms
// negative sum subarray
// from i-th index
int index = b_search(pre_sum,
m, i);
// If a subarray is found
// starting from i-th index
if (index != -1)
return { i, index };
}
}
// Return -1 if no such
// subarray is present
return { -1 };
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, -1, 3, -4, 3, -5 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
vector<int> res = findSubarray(arr, n);
// If subarray does not exist
if (res[0] == -1)
cout << "-1" << endl;
// If the subarray exists
else {
cout << res[0]
<< " " << res[1];
}
return 0;
}
0 6
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array
Publicación traducida automáticamente
Artículo escrito por godaraji47 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA