겹치는 연속 하위 배열의 최대 합 K

난이도 하드
자주 묻는 질문 코드네이션 작은 골짜기 Facebook GE 헬스 케어 구글 퀄컴
배열 동적 프로그래밍조회수 20

문제 정책

"중첩 된 연속 하위 배열의 최대 합 K"문제는 정수 배열이 제공된다는 것을 나타냅니다. 합이 최대가되도록 k-subarray의 최대 합을 구합니다. 이러한 k-subarray가 겹칠 수 있습니다. 따라서 다른 하위 배열 중에서 합이 최대가되도록 k-subarray를 찾아야합니다.

겹치는 연속 하위 배열의 최대 합 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 개의 최대 합을 구하도록 요청합니다. 그래서 우리가 카단 연산. 문제를 해결할 수 없습니다. Kadane의 알고리즘을 사용하여 최대 합계를 찾을 수 있기 때문입니다. 그러나 그것은 두 번째 최대 값, 세 번째 최대 값 및 기타를 찾을 수 없습니다. Kadane의 알고리즘은 주로 첫 번째 최대 값을 찾는 데 초점을 맞추고 다음 최대 하위 배열 합계를 찾는 것을 목표로하지 않습니다. 여기서 우리는 minimumKSum과 maximumKSum의 두 배열을 만듭니다. 접두사 합계 배열을 사용하여 현재 인덱스에 대한 하위 배열의 합계를 찾습니다. 최소 배열 KSum은 하위 배열의 k 최소 합을 유지합니다. 배열 maximumKSum은 하위 배열의 k 최대 합을 유지합니다. 이제 각 인덱스에 대해 minimumKSum 및 maximumKSum 배열을 업데이트합니다. 배열을 통과 한 후 응답은 maximumKSum 내부에 저장됩니다.

암호

겹치는 연속 하위 배열의 K 최대 합을 찾는 C ++ 코드

#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

겹치는 연속 하위 배열의 K 최대 합계를 찾는 Java 코드

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

공간 복잡성: 의 위에)

공간의 상한을 표시하는 inputArray에 입력을 저장합니다. 따라서 솔루션의 공간 복잡성은 선형입니다.

Translate »