重疊的連續子數組的K個最大和  


難度級別
經常問 編碼國家 戴爾 Facebook GE醫療集團 谷歌 高通公司
排列 動態編程

問題陳述  

問題“重疊的連續子數組的K個最大和”表示給您一個整數數組。 找到k個子數組的最大和,以使其總和最大。 這些k子數組可能重疊。 因此,我們需要找到k個子數組,使它們的總和在其他子數組中最大。

例  

重疊的連續子數組的K個最大和

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

說明:sum = 50的子數組具有最大值。 此後,如果我們向左或向右方向求和,則總和減小。 因此,如果我們向左移動。 我們可以再次得到50,因為-10和10互相抵消。 但是,如果我們朝著正確的方向前進,我們的總和只會不斷減少。 因此,這是我們可以獲得的最佳答案。

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

說明:在這裡,如果我們將兩個數字中的任何一個組合,將導致更糟糕的解決方案。 因此,選擇一個數字會更好。 因此,我們將選擇單個數字-1 -2 -3。 任何其他組合都會給我們帶來更糟糕的結果。

重疊連續子數組的K個最大和的方法  

問題要求我們在所有子數組的所有和中找到k個最大和。 所以,如果我們考慮使用 卡丹的 算法。 我們將無法解決問題。 因為可以使用Kadane的算法來找到最大和。 但這將無法找到第二個最大值,第三個最大值和其他最大值。 Kadane的算法主要側重於找到第一個最大值,而不是尋找下一個最大子數組和。 在這裡,我們創建了minimumKSum和maximumKSum的兩個數組。 我們將使用前綴總和數組來查找當前索引的子數組的總和。 數組minimumKSum保留子數組的k個最小和。 數組maximumKSum保留子數組的k個最大和。 現在,對於每個索引,我們更新minimumKSum和maximumKSum數組。 遍歷數組後,答案存儲在maximumKSum中。

也可以看看
合併兩個排序的鍊錶

推薦碼  

C ++代碼查找重疊的連續子數組的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)

插入最小KSum和插入最大KSum需要O(k)時間。 我們正在循環遍歷數組每個元素的循環內執行此過程。 因此,整體時間複雜度為 O(k * n).

也可以看看
從四個排序數組中計算四倍,其總和等於給定值x

空間複雜度: 上)

我們將輸入存儲在inputArray中,該輸入標誌著空間的上限。 因此,解決方案的空間複雜度是線性的。