Dado um array arr [] que consiste em N inteiros, a tarefa é encontrar os índices inicial e final do primeiro subarray com uma Soma Negativa. Imprima “-1” se tal subarray não existir.

Nota: No caso de vários subarrayes de soma negativa em um determinado array, o primeiro subarray se refere ao subarray com o índice inicial mais baixo.

Exemplos:

Entrada: arr [] = {3, 3, -4, -2}
Saída: 1 2
Explicação:
O primeiro subarray com soma negativa é do índice 1 a 2 que é arr [1] + arr [2] = -1.

Entrada: arr [] = {1, 2, 3, 10}.
Saída: -1
Explicação:
Não existe nenhum Subarray com soma negativa.

Abordagem ingênua: A abordagem ingênua é gerar todos os subarrays da esquerda para a direita no array e verificar se algum desses subarrays tem uma soma negativa ou não. Se sim, então imprima o índice inicial e final desse subarray.

Complexidade de tempo: O (N ² )
Espaço auxiliar: O (1)

Abordagem eficiente: A ideia é resolver o problema usando Prefix Sum and Hashing . Abaixo estão as etapas:

1. Calcule a soma do prefixo da array e armazene-a no HashMap .
2. Itere através da array e para cada i ^ésimo índice, onde i varia de [0, N - 1] , verifique se o elemento no i ^ésimo índice é negativo ou não. Nesse caso, arr [i] é o subarray necessário.
3. Caso contrário, encontre um índice começando em i + 1, onde a soma do prefixo é menor que a soma do prefixo até i .
4. Se algum desses índices for encontrado na etapa acima, a subarray de índices {i, índice} fornece a primeira subarray negativa.
5. Se nenhum subarray for encontrado, imprima “-1” . Caso contrário, imprima o subarray obtido.

Abaixo está a implementação da abordagem acima:

// 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

Complexidade de tempo: O (N * log N)
Espaço auxiliar: O (N)