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

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

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

"중첩 된 연속 하위 배열의 최대 합 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 »