Рубрики

Самый большой подмассив, имеющий сумму больше k

Учитывая массив целых чисел и значение k, найдите длину наибольшего подмассива, имеющего сумму, превышающую k.

Примеры:

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}.

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

Простое решение состоит в том, чтобы один за другим рассмотреть каждый подмассив и найти его сумму. Если сумма больше, чем k, сравните длину этого подмассива с максимальной найденной длиной. Временная сложность этого решения составляет O (n 2 ).

Эффективным решением является использование префиксной суммы и двоичного поиска. Идея состоит в том, чтобы обойти массив и сохранить сумму префикса и соответствующий индекс массива в векторе пар. После нахождения суммы префикса сортируйте вектор в порядке возрастания суммы префикса и по тому же значению суммы префикса сортируйте по индексу. Создайте еще один массив minInd [], в котором minInd [i] хранит минимальное значение индекса в диапазоне [0..i] в векторной сумме отсортированного префикса. После этого начните обход массива arr [] и сохраните сумму подмассива arr [0..i] в сумме. Если сумма больше k, то наибольшим подмассивом, имеющим сумму больше k, является arr [0..i] длиной i + 1. Если сумма меньше или равна k, то значение больше или равно к k + 1 — сумма должна быть добавлена к сумме, чтобы она была как минимум k + 1. Пусть это значение будет х. Чтобы добавить x к сумме, из нее можно вычесть -x, потому что sum — (- x) = sum + x. Таким образом, необходимо найти префиксный массив arr [0..j] (j <i), имеющий сумму не более -x (не более -x, потому что k + 1-сумма является наименьшим значением, теперь его отрицательное значение принимается так, это будет максимально допустимое значение). Результирующий подмассив arr [j + 1..i] должен быть как можно большим. Для этого значение j должно быть минимально возможным. Таким образом, проблема сводится к поиску суммы префикса, имеющей значение не более -x, и его конечный индекс должен быть минимальным. Чтобы найти сумму префикса, можно выполнить двоичный поиск по вектору суммы префикса. Пусть индекс ind обозначает, что в векторе суммы префиксов все значения суммы префикса вплоть до индекса ind меньше или равны -x. Минимальное значение индекса в диапазоне [0..ind] — minInd [ind]. Если minInd [ind] больше, чем i, то не существует подмассива с суммой -x в диапазоне [0..i-1]. Иначе arr [minInd [ind] + 1..i] имеет сумму больше k. Сравните его длину с максимальной найденной длиной.

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

C ++

// Программа CPP для поиска наибольшего подмассива
// имея сумму больше k.
#include <bits/stdc++.h>

using namespace std;

  
// Функция сравнения, используемая для сортировки вектора preSum.

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;

}

  
// Функция для поиска индекса в векторе preSum, до которого
// все значения суммы префикса меньше или равны val.

int findInd(vector<pair<int, int> >& preSum, int n,

                                            int val)

{

  

    // Начальный и конечный индекс пространства поиска.

    int l = 0;

    int h = n - 1;

    int mid;

  

    // Для сохранения необходимого значения индекса.

    int ans = -1;

  

    // Если среднее значение меньше или равно

    // val, тогда индекс может лежать в середине + 1..n

    // иначе он лежит в 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;

}

  
// Функция для поиска наибольшего подмассива, имеющего сумму
// больше или равно k.

int largestSub(int arr[], int n, int k)

{

    int i;

  

    // Длина наибольшего подмассива.

    int maxlen = 0;

  

    // Вектор для хранения пары префиксных сумм

    // и соответствующее конечное значение индекса.

    vector<pair<int, int> > preSum;

  

    // Для сохранения текущего значения префикса sum.

    int sum = 0;

  

    // Для хранения минимального значения индекса в диапазоне

    // 0..i вектора preSum.

    int minInd[n];

  

    // Вставить значения в вектор preSum.

    for (i = 0; i < n; i++) {

        sum = sum + arr[i];

        preSum.push_back({ sum, i });

    }

  

    sort(preSum.begin(), preSum.end(), compare);

  

    // Обновление массива minInd.

    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];

  

        // Если сумма больше k, тогда отвечаем

        // это я + 1.

        if (sum > k)

            maxlen = i + 1;

  

        // Если сумма меньше или равна k, то

        // найти, есть ли префиксный массив с суммой

        // это необходимо добавить к текущей сумме

        // сделать его значение больше k. Если да, то

        // сравниваем длину обновленного подмассива с

        // найдена максимальная длина

        else {

            int ind = findInd(preSum, n, sum - k - 1);

            if (ind != -1 && minInd[ind] < i)

                maxlen = max(maxlen, i - minInd[ind]);

        }

    }

  

    return maxlen;

}

  
// Код драйвера.

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;

}

python3

# Python3 программа для поиска наибольшего подмассива
# имеющий сумму больше k.

  
# Функция сравнения используется для
# sort preSum vector.

def compare(a, b): 

  

    if a[0] == b[0]: 

        return a[1] < b[1

  

    return a[0] < b[0

  
# Функция для поиска индекса в векторе preSum
# до которого все значения суммы префикса меньше
# чем или равно val.

def findInd(preSum, n, val): 

  

    # Начальный и конечный индекс

    # пространство поиска.

    l, h = 0, n - 1

  

    # Для сохранения необходимого значения индекса.

    ans = -1

  

    # Если среднее значение меньше или равно

    # до val, тогда индекс может лежать в середине + 1..n

    # иначе он лежит в 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 

  
# Функция для поиска наибольшего подмассива, имеющего
# сумма больше или равна k.

def largestSub(arr, n, k): 

  

    # Длина наибольшего подмассива.

    maxlen = 0

  

    # Вектор для хранения пары префиксных сумм

    # и соответствующее конечное значение индекса.

    preSum = [] 

  

    # Для сохранения текущего значения префикса sum.

    Sum = 0

  

    # Хранить минимальное значение индекса в диапазоне

    # 0..i вектора preSum.

    minInd = [None] * (n) 

  

    # Вставить значения в вектор preSum.

    for i in range(0, n): 

        Sum = Sum + arr[i] 

        preSum.append([Sum, i]) 

      

    preSum.sort()

      

    # Обновление массива minInd.

    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] 

  

        # Если сумма больше k, то

        # ответ: я + 1.

        if Sum > k:

            maxlen = i + 1

  

        # Если сумма меньше или равна k,

        # тогда найдите, есть ли префиксный массив

        # с суммой, которую нужно добавить в

        # текущая сумма для увеличения значения

        # чем к. Если да, то сравните длину

        # обновленного подмассива с максимумом

        # длина найдена до сих пор.

        else:

            ind = findInd(preSum, n, Sum - k - 1

            if ind != -1 and minInd[ind] < i: 

                maxlen = max(maxlen, i - minInd[ind]) 

  

    return maxlen 

  
# Код драйвера.

if __name__ == "__main__":

  

    arr = [-2, 1, 6, -3

    n = len(arr) 

  

    k = 5

  

    print(largestSub(arr, n, k)) 

      
# Этот код добавлен
# от Rituraj Jain

Выход:

2

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

Рекомендуемые посты:

Самый большой подмассив, имеющий сумму больше k

0.00 (0%) 0 votes