Первый подмассив с отрицательной суммой из данного массива

Опубликовано: 1 Января, 2022

Для массива arr [], состоящего из N целых чисел, задача состоит в том, чтобы найти начальный и конечный индексы первого подмассива с отрицательной суммой. Выведите «-1», если такой подмассив не существует.

Примечание. В случае нескольких подмассивов с отрицательной суммой в данном массиве первый подмассив относится к подмассиву с наименьшим начальным индексом.

Примеры:

Input: arr[] = {3, 3, -4, -2}
Output: 1 2
Explanation:
The first subarray with negative sum is from index 1 to 2 that is arr[1] + arr[2] = -1.
Input: arr[] = {1, 2, 3, 10}.
Output: -1
Explanation:
No Subarray with negative sum exists.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход: наивный подход состоит в том, чтобы сгенерировать все подмассивы слева направо в массиве и проверить, имеет ли какой-либо из этих подмассивов отрицательную сумму или нет. Если да, то выведите начальный и конечный индексы этого подмассива.

Сложность времени: O (N ² )
Вспомогательное пространство: O (1)

Эффективный подход: идея состоит в том, чтобы решить проблему с помощью суммы префиксов и хеширования. Ниже приведены шаги:

Вычислите сумму префиксов массива и сохраните ее в HashMap .
Выполните итерации по массиву и для каждого i- ^го индекса, где i находится в диапазоне [0, N - 1] , проверьте, является ли элемент с i- ^м индексом отрицательным или нет. Если это так, то arr [i] - это требуемый подмассив.
В противном случае найдите индекс, начинающийся с i + 1, где сумма префиксов меньше суммы префиксов до i .
Если какой-либо такой индекс найден на предыдущем шаге, то подмассив из индексов {i, index} дает первый отрицательный подмассив.
Если такой подмассив не найден, выведите «-1» . В противном случае выведите полученный подмассив.

Ниже представлена реализация описанного выше подхода:

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

Сложность времени: O (N * log N)
Вспомогательное пространство: O (N)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Олимпиады по программированию Алгоритмы

Первый подмассив с отрицательной суммой из данного массива

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

C ++

РЕКОМЕНДУЕМЫЕ СТАТЬИ