특정 요소를 제외한 최대 부분 배열 합계


자주 묻는 질문 수행자 코드네이션 지시 JP 모건 퀄컴
배열 이진 검색 동적 프로그래밍 기술 스크립터조회수 80

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

문제 정책

배열이 주어졌고 특정 요소를 제외한 최대 부분 배열 합계를 찾아야합니다. 즉, 우리가 고려하고있는 부분 배열이 제외하라는 요소를 포함하지 않도록 부분 배열의 최대 합을 찾아야합니다.

특정 요소를 제외한 최대 부분 배열 합의 예

특정 요소를 제외한 최대 부분 배열 합계

Array = {1,2,3,4,5}
Elements to be excluded = {2,3,5}
4

설명 : 여기서는 하위 배열에 제외 된 요소가 포함되도록 하위 배열을 선택할 수 없습니다. 따라서 우리는 1 또는 4를 선택할 수 있습니다. 그러나 4가 1보다 크므로 4가 답입니다. Ans 문제는 하위 시퀀스 대신 하위 배열을 요청하는 것입니다. 그렇지 않으면 우리는 우리의 대답에서도 1을 취했을 것입니다.

 

Array = {1,-1,10,-6,2}
Elements to be excluded = {10}
2

설명 : 여기서 우리는 어떤 부정적인 요소도 선택해서는 안되며 10 개를 하위 배열에 넣을 수 없습니다. 다시 한 번, 1 또는 2를 선택하는 두 가지 선택이 있습니다. 2> 1이므로 답은 2입니다.

 

특정 요소를 제외한 최대 부분 배열 합계를 찾는 방법

순진한 접근

모든 하위 배열을 쉽게 고려한 다음 하위 배열에 제외 할 요소가 포함되어 있는지 확인할 수 있습니다. 그러한 요소가 포함되어 있지 않으면 단순히 합계를 찾고 답변을 업데이트합니다. 그러나이 접근 방식은 효율적이지 않습니다. 효율적인 접근 방식은 Kadane의 알고리즘 최대 하위 배열을 찾습니다. 그러나 우리는 제외 할 요소를 포함하지 않는 부분에서만 Kadane을 실행합니다. 이제 문제는 요소를 제외해야하는지 여부를 어떻게 찾을 수 있는가입니다. 제외 할 요소 배열을 반복 할 수 있습니다. 배열에 현재 요소가 포함되어 있으면 선택하지 않고 계속 진행합니다. 그러나이 접근 방식은 더욱 최적화 될 수 있으며 이는 효율적인 접근 방식 섹션에서 설명합니다.

효율적인 접근

우리는 이미 Kadane의 알고리즘을 사용하여 하위 배열의 합계를 찾을 것이라고 논의했습니다. 현재 요소가 제외 할 요소 중 하나 일 때마다. 해당 요소를 무시하고 계속 진행하면서 currentSum을 0으로 업데이트합니다. 이제 현재 요소를 제외해야하는지 여부를 찾는 데 여전히 문제가 있습니다. 요소를 제외해야하는지 여부를 확인합니다. 해시 세트 또는 무순 세트를 사용합니다. 집합에 현재 요소가 포함되어 있으면 건너 뛰고 계속 진행합니다. 따라서 명확하게 말하면이 unorder_set에는 제외 할 요소가 포함되어 있습니다.

특정 요소를 제외한 최대 부분 배열 합계를 찾는 코드

C ++ 코드

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

int main(){
  int testCases;cin>>testCases;
  while(testCases--){
    int inputSize;cin>>inputSize;
    int input[inputSize];
    for(int i=0;i<inputSize;i++)
      cin>>input[i];
    int excludedElementsSize;cin>>excludedElementsSize;
    unordered_set<int> excludedElements;
    for(int i=0;i<excludedElementsSize;i++){
      int excludedElement;cin>>excludedElement;
      excludedElements.insert(excludedElement);
    }

    int currentSum = 0, maximumSum = 0;

    for(int i=0;i<inputSize;i++){
      if(excludedElements.count(input[i])){
        currentSum = 0;
      } else {
          currentSum = max(currentSum + input[i], input[i]);
          maximumSum = max(currentSum, maximumSum);
      }
    }
    cout<<maximumSum<<endl;
  }
}
1
5
1 2 3 4 5
3
2 3 4
4

 

자바 코드

import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
    	int testCases = sc.nextInt();
    	while(testCases-- > 0){
    		int inputSize = sc.nextInt();
    		int input[] = new int[inputSize];
    		for(int i=0;i<inputSize;i++)
    		    input[i] = sc.nextInt();
    		int excludedElementsSize = sc.nextInt();
    		HashSet<Integer> excludedElements = new HashSet<Integer>();
    		for(int i=0;i<excludedElementsSize;i++){
    		    int excludedElement = sc.nextInt();
    	       	    excludedElements.add(excludedElement);
    		}
    
    		int currentSum = 0, maximumSum = 0;
    
    		for(int i=0;i<inputSize;i++){
    	            if(excludedElements.contains(input[i])){
    			currentSum = 0;
                    } else {
                        currentSum = Math.max(currentSum + input[i], input[i]);
                        maximumSum = Math.max(currentSum, maximumSum);
                    }
    		}
    
    		System.out.println(maximumSum);
        }
    }
}
1
5
1 2 3 4 5
3
2 3 4
4

 

복잡성 분석

시간 복잡성: 의 위에)

단순히 배열을 순회하고 제외 할 요소를 저장하기 위해 unorder_set 또는 HashSet을 사용했기 때문입니다. 선형 시간 복잡도가 O (N) 인 알고리즘이 있습니다.

공간 복잡성: 의 위에)

HashSet 또는 unrdered_set은 키-값 쌍의 수에 비례하여 메모리를 사용하며 그 외에는 단일 배열을 사용했습니다. 따라서 우리는 O (N)의 공간 복잡성을가집니다.

균열 시스템 설계 인터뷰
Translate »