Рубрики

Максимальная сумма двух неперекрывающихся подмассивов заданного размера

Для данного массива нам нужно найти два подмассива с определенной длиной K, чтобы сумма этих подмассивов была максимальной среди всех возможных вариантов выбора подмассивов.
Примеры:

Input : arr[] = [2, 5, 1, 2, 7, 3, 0]
        K = 2
Output : 2 5
         7 3
We can choose two arrays of maximum sum
as [2, 5] and [7, 3], the sum of these two 
subarrays is maximum among all possible 
choices of subarrays of length 2.

Input : arr[] = {10, 1, 3, 15, 30, 40, 4, 50, 2, 1}
        K = 3
Output : 3 15 30 
         40 4 50 

Мы можем решить эту проблему аналогично методу двух указателей. Сначала мы сохраняем сумму префикса в отдельном массиве, чтобы любая сумма подмассива могла быть вычислена за постоянное время. После этого мы инициализируем два наших подмассива из индексов (N — 2K) и (N — K), где N — длина массива, а K — необходимая длина подмассива. Затем мы будем двигаться от (N — 2K) индекса к 0, и каждый раз, когда мы будем проверять, больше ли сумма подмассива в текущем индексе и сумма подмассива в (текущий индекс + K), чем ранее выбранный подрешетку, или нет, обновите суммирование. Здесь мы видим, что, поскольку нам нужно максимизировать нашу сумму, мы можем обрабатывать оба подмассива независимо. В каждом индексе мы проверим сумму подмассива в текущем индексе и сумму подмассива на расстоянии K, и мы выберем максимальную сумму независимо и обновим окончательный ответ как суммирование обоих этих массивов. В приведенном ниже коде индекс также берется с суммой в виде пары для фактической печати подмассивов. Общая временная сложность решения будет линейной.
Пожалуйста, смотрите код ниже для лучшего понимания.

C ++

// C ++ программа для получения максимальной суммы двух непересекающихся
// подмассивы одинаковой заданной длины
#include <bits/stdc++.h>

using namespace std;

  
// Служебный метод для получения суммы подмассива
// из индекса i в j

int getSubarraySum(int sum[], int i, int j)

{

    if (i == 0)

        return sum[j];

    else

        return (sum[j] - sum[i - 1]);

}

  
// Метод печатает два непересекающихся подмассива
// длина K, чья сумма максимальна

void maximumSumTwoNonOverlappingSubarray(int arr[],

                                      int N, int K)

{

    int sum[N];

  

    // заполнение массива префиксных сумм

    sum[0] = arr[0];

    for (int i = 1; i < N; i++)

        sum[i] = sum[i - 1] + arr[i];

  

    // инициализация подмассивов из индексов (N-2K) и (NK)

    pair<int, int> resIndex = make_pair(N - 2 * K, N - K);

  

    // инициализация итоговой суммы из вышеуказанных сумм подмассива

    int maxSum2Subarray = getSubarraySum(sum, N - 2 * K, N - K - 1) +

                          getSubarraySum(sum, N - K, N - 1);

  

    // сохраняем второй максимум подмассива и его начальный индекс

    pair<int, int> secondSubarrayMax = make_pair(N - K,

                          getSubarraySum(sum, N - K, N - 1));

  

    // цикл от N-2K-1 к 0

    for (int i = N - 2 * K - 1; i >= 0; i--)

    {

        // получаем сумму подмассива из (текущий индекс + K)

        int cur = getSubarraySum(sum, i + K, i + 2  * K - 1);

  

        // если (текущий индекс + K) сумма больше, чем обновить

        // secondSubarrayMax

        if (cur >= secondSubarrayMax.second)

            secondSubarrayMax = make_pair(i + K, cur);

  

        // теперь получаем полную сумму (сумму обоих подмассивов)

        cur = getSubarraySum(sum, i, i + K - 1) +

              secondSubarrayMax.second;

  

        // если больше, то обновляем основной результат

        if (cur >= maxSum2Subarray)

        {

            maxSum2Subarray = cur;

            resIndex = make_pair(i, secondSubarrayMax.first);

        }

    }

  

    // печать актуальных подмассивов

    for (int i = resIndex.first; i < resIndex.first + K; i++)

        cout << arr[i] << " ";

    cout << endl;

  

    for (int i = resIndex.second; i < resIndex.second + K; i++)

        cout << arr[i] << " ";

    cout << endl;

}

  
// Код драйвера для тестирования вышеуказанных методов

int main()

{

    int arr[] = {2, 5, 1, 2, 7, 3, 0};

    int N = sizeof(arr) / sizeof(int);

  

    // K будет дано так, что (N> = 2K)

    int K = 2;

  

    maximumSumTwoNonOverlappingSubarray(arr, N, K);

  

    return 0;

}

Джава

// Java-программа для получения максимальной суммы двух непересекающихся
// подмассивы одинаковой заданной длины

class GFG 

{

  

static class pair

    int first, second; 

    public pair(int first, int second) 

    

        this.first = first; 

        this.second = second; 

    

  
// Служебный метод для получения суммы подмассива
// из индекса i в j

static int getSubarraySum(int sum[], 

                          int i, int j)

{

    if (i == 0)

        return sum[j];

    else

        return (sum[j] - sum[i - 1]);

}

  
// Метод печатает два непересекающихся подмассива
// длина K, чья сумма максимальна

static void maximumSumTwoNonOverlappingSubarray(int arr[],

                                                int N, int K)

{

    int []sum = new int[N];

  

    // заполнение массива префиксных сумм

    sum[0] = arr[0];

    for (int i = 1; i < N; i++)

        sum[i] = sum[i - 1] + arr[i];

  

    // инициализация подмассивов из

    // (N-2K) и (NK) индексы

    pair resIndex = new pair(N - 2 * K, N - K);

  

    // инициализация итоговой суммы из вышеуказанных сумм подмассива

    int maxSum2Subarray = getSubarraySum(sum, N - 2 * K, 

                                              N - K - 1) +

                          getSubarraySum(sum, N - K, N - 1);

  

    // сохраняем второй максимум подмассива и

    // его начальный индекс

    pair secondSubarrayMax = new pair(N - K, 

                       getSubarraySum(sum, N - K, N - 1));

  

    // цикл от N-2K-1 к 0

    for (int i = N - 2 * K - 1; i >= 0; i--)

    {

        // получаем сумму подмассива из (текущий индекс + K)

        int cur = getSubarraySum(sum, i + K, i + 2 * K - 1);

  

        // если (текущий индекс + K) сумма больше

        // затем обновляем secondSubarrayMax

        if (cur >= secondSubarrayMax.second)

            secondSubarrayMax = new pair(i + K, cur);

  

        // теперь получаем полную сумму (сумму обоих подмассивов)

        cur = getSubarraySum(sum, i, i + K - 1) +

            secondSubarrayMax.second;

  

        // если больше, то обновляем основной результат

        if (cur >= maxSum2Subarray)

        {

            maxSum2Subarray = cur;

            resIndex = new pair(i, secondSubarrayMax.first);

        }

    }

  

    // печать актуальных подмассивов

    for (int i = resIndex.first; 

             i < resIndex.first + K; i++)

        System.out.print(arr[i] + " ");

    System.out.println();

  

    for (int i = resIndex.second;

             i < resIndex.second + K; i++)

        System.out.print(arr[i] + " ");

    System.out.println();

}

  
// Код драйвера для тестирования вышеуказанных методов

public static void main(String[] args)

{

    int arr[] = {2, 5, 1, 2, 7, 3, 0};

    int N = arr.length;

  

    // K будет дано так, что (N> = 2K)

    int K = 2;

  

    maximumSumTwoNonOverlappingSubarray(arr, N, K);

}

  
// Этот код предоставлен Rajput-Ji

python3

# Программа Python3 для получения максимальной суммы два
# неперекрывающиеся подмассивы одинаковой заданной длины

  
# Утилита для получения суммы
# подмассив из индекса i в j

def getSubarraySum(Sum, i, j): 

  

    if i == 0:

        return Sum[j] 

    else:

        return Sum[j] - Sum[i - 1

  
# Метод печатает два непересекающихся подмассива
№ длины K, чья сумма максимальна

def maximumSumTwoNonOverlappingSubarray(arr, N, K): 

  

    Sum = [None] * N

  

    # заполнение префикса Сумма массива

    Sum[0] = arr[0

    for i in range(1, N): 

        Sum[i] = Sum[i - 1] + arr[i] 

  

    # Инициализация подмассивов из

    # (N-2K) и (NK) индексы

    resIndex = (N - 2 * K, N - K) 

  

    # инициализация результата Сумма сверху подмассива Суммы

    maxSum2Subarray = (getSubarraySum(Sum, N - 2 * K, N - K - 1) + 

                       getSubarraySum(Sum, N - K, N - 1)) 

  

    # сохранение второго максимума подмассива и его начального индекса

    secondSubarrayMax = (N - K, getSubarraySum(Sum, N - K, N - 1)) 

  

    # петля от N-2K-1 к 0

    for i in range(N - 2 * K - 1, -1, -1): 

      

        # получить сумму массива из (текущий индекс + K)

        cur = getSubarraySum(Sum, i + K, i + 2 * K - 1

  

        # if (текущий индекс + K) Сумма больше

        # чем обновить secondSubarrayMax

        if cur >= secondSubarrayMax[1]:

            secondSubarrayMax = (i + K, cur) 

  

        # теперь получается полная сумма (сумма обоих подмассивов)

        cur = (getSubarraySum(Sum, i, i + K - 1) + 

                           secondSubarrayMax[1]) 

  

        # Если больше, обновите основной результат

        if cur >= maxSum2Subarray:

          

            maxSum2Subarray = cur 

            resIndex = (i, secondSubarrayMax[0]) 

  

    # печать актуальных подмассивов

    for i in range(resIndex[0], resIndex[0] + K): 

        print(arr[i], end = " "

    print() 

  

    for i in range(resIndex[1], resIndex[1] + K): 

        print(arr[i], end = " "

    print()

  
Код водителя

if __name__ == "__main__":

  

    arr = [2, 5, 1, 2, 7, 3, 0

    N = len(arr)

  

    # K будет дано так, что (N> = 2K)

    K = 2

  

    maximumSumTwoNonOverlappingSubarray(arr, N, K) 

  
# Этот код предоставлен Rituraj Jain

Выход:

2 5
7 3

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Максимальная сумма двух неперекрывающихся подмассивов заданного размера

0.00 (0%) 0 votes