K максимальні суми суміжних суміжних підмасивів


Рівень складності Жорсткий
Часто запитують у CodeNation Dell Facebook GE Healthcare Google компанія Qualcomm
масив Динамічне програмування

Постановка проблеми

У задачі “K максимальні суми суміжних суміжних підмасивів” зазначено, що вам дано масив цілих чисел. Знайдіть максимальну суму k-підмасивів таку, щоб їх сума була максимальною. Ці k-підмасиви можуть перекриватися. Отже, нам потрібно знайти k-підмасивів, щоб їх сума була максимальною серед інших підмасивів.

Приклад

K максимальні суми суміжних суміжних підмасивів

arr = {10,-10,20,30,-1,-2}, k = 2
50 50

Пояснення: Підмасив із сумою = 50 має максимальне значення. Після цього, якщо ми вліво чи вправо, сума зменшується. Отже, якщо рухатись у лівому напрямку. Ми можемо знову отримати суму 50, оскільки -10 і 10 скасовують один одного. Але якщо ми рухатимемось у правильному напрямку, наша сума буде лише зменшуватися. Отже, це найкраща можлива відповідь, яку ми могли б отримати.

arr = {-1,-2,-3,-4}, k = 3
-1 -2 -3

Пояснення: Тут, якщо ми поєднаємо будь-яке з двох чисел, це призведе до гіршого рішення. Отже, вибір одного номера буде кращим. Таким чином, ми виберемо одиничні числа -1 -2 -3. Будь-яка інша комбінація дасть нам гірший результат.

Підхід для K максимальних сум перекриваються суміжних підмасивів

Завдання просить нас знайти k максимальних сум серед усіх сум усього підмасиву. Отже, якщо ми думаємо використовувати Кадане алгоритм. Ми не зможемо вирішити проблему. Оскільки за допомогою алгоритму Кадана можна знайти максимальну суму. Але це не зможе знайти другий максимум, третій максимум та інші. Алгоритм Кадане в основному зосереджений на пошуку першого максимуму і не має на меті знайти наступну максимальну суму підмасиву. Тут ми створюємо два масиви minimumKSum і maximumKSum. Ми використаємо префіксний масив sum, щоб знайти суму підмасивів для поточного індексу. Масив minimumKSum зберігає k мінімальну суму підмасивів. Масив maximumKSum зберігає k максимальну суму підмасивів. Тепер для кожного індексу ми оновлюємо масиви minimumKSum та maximumKSum. Після обходу масиву відповідь зберігається всередині maximumKSum.

код

Код С ++ для пошуку K максимальних сум суміжних суміжних масивів

#include<bits/stdc++.h>
using namespace std;

void kMaxSubArrays(vector<int> input, int k)
{
  int n = input.size();
  vector<int> prefixSum(n);
    prefixSum[0] = input[0];
    for(int i=1;i<n;i++)
        prefixSum[i] += prefixSum[i-1] + input[i];

  vector<int> minimumKSum(k, INT_MAX);
  minimumKSum[0] = 0;

  vector<int> maximumKSum(k, INT_MIN);
  vector<int> currentSum(k);

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < k; j++) {
      if(prefixSum[i] < 0 && minimumKSum[j]==INT_MAX)
            currentSum[j]=(-prefixSum[i])-minimumKSum[j];
        else
                currentSum[j] = prefixSum[i] - minimumKSum[j];
    }
        int j = 0;
        for (int l = 0; l < k; l++) {
            if (currentSum[j] > maximumKSum[l]) {
                maximumKSum.insert(maximumKSum.begin() + l, currentSum[j]);
                maximumKSum.erase(maximumKSum.begin() + k);
                j++;
            }
        }
    for (int j = 0; j < k; j++) {
            if (prefixSum[i] < minimumKSum[j]) {
                minimumKSum.insert(minimumKSum.begin() + j, prefixSum[i]);
                minimumKSum.erase(minimumKSum.begin() + k);
                break;
            }
        }
  }

  for (int element : maximumKSum)
    cout<<element<<" ";
}

int main()
{
  int inputSize;cin>>inputSize;
  vector<int> input(inputSize);
  for(int i=0;i<inputSize;i++)cin>>input[i];
  int k;cin>>k;
  kMaxSubArrays(input, k);
}
6
10 -10 20 30 -1 -2
2
50 50

Код Java для пошуку K максимальних сум перекриваючих суміжних підмасивів

import java.util.*;

class Main{
    
    static void kMaxSubArrays(int input[], int k)
    {
    	int n = input.length;
    	int prefixSum[] = new int[n];
        prefixSum[0] = input[0];
        for(int i=1;i<n;i++)
            prefixSum[i] += prefixSum[i-1] + input[i];
    
    	int maximumKSum[] = new int[k];
    	for(int i=0;i<k;i++)
    	    maximumKSum[i] = Integer.MIN_VALUE;
    
    	int minimumKSum[] = new int[k];
    	for(int i=0;i<k;i++)
    	    minimumKSum[i] = Integer.MAX_VALUE;
    	minimumKSum[0] = 0;
    	
    	int currentSum[] = new int[k];
    	for(int i=0;i<k;i++)
    	    currentSum[i] = 0;
    
    	for (int i=0;i<n;i++) {
    		for (int j=0;j<k;j++) {
    			if(prefixSum[i] < 0 && minimumKSum[j]==Integer.MAX_VALUE)
    		        currentSum[j]=(-prefixSum[i])-minimumKSum[j];
    		    else
                    currentSum[j] = prefixSum[i] - minimumKSum[j];
    		}
            int j = 0;
            for (int l = 0; l < k; l++) {
                if (currentSum[j] > maximumKSum[l]) {
                    maximumKSum[l] = currentSum[j];
                    for(int z = l+1;z<k;z++)
                        maximumKSum[z] = maximumKSum[z-1];
                    j++;
                }
            }
    		for (j = 0; j < k; j++) {
                if (prefixSum[i] < minimumKSum[j]) {
                    minimumKSum[j] = prefixSum[i];
                    for(int z = j+1;z<k;z++)
                        minimumKSum[z] = minimumKSum[z-1];
                    break;
                }
            }
    	}
    
    	for(int i=0;i<k;i++)
    		System.out.print(maximumKSum[i]+" ");
    }
    
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
    	int inputSize = sc.nextInt();
    	int input[] = new int[inputSize];
    	for(int i=0;i<inputSize;i++)input[i] = sc.nextInt();
    	int k = sc.nextInt();
    	kMaxSubArrays(input, k);
    }
}
6
10 -10 20 30 -1 -2
2
50 50

Аналіз складності

Складність часу: O (k * N)

Вставка в minimumKSum і вставка в maximumKSum займають час O (k). І ми робимо цей процес всередині циклу, який зациклюється над кожним елементом масиву. Отже, загальна складність часу становить O (k * n).

Складність простору: O (N)

Ми зберігаємо вхідні дані у inputArray, який позначає верхню межу простору. Таким чином, просторова складність рішення є лінійною.