최대 합 바이 토닉 서브 어레이

난이도 중급
자주 묻는 질문 시스코 드 쇼 작은 골짜기 포카이트 골드만 삭스 그루퍼 IBM 알레그로 Quora Yahoo
배열 동적 프로그래밍조회수 59

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

문제 정책

An 정렬 n 개의 정수가 우리에게 주어집니다. 우리는 최대 합계 비트 배열 하위 배열. 비 토닉 하위 배열은 요소가 특정 순서로 배열되는 하위 배열 일뿐입니다. 첫 번째 요소는 오름차순이되고 내림차순이됩니다. 따라서 a, a + 1, a + 4, a + 7, a-9, a-11과 같은 것입니다. 여기서 상수는 배열에 부과 된 조건을 만족하는 난수 일뿐입니다. 이것은 단지 그들의 순서를 보여주는 것입니다. 

 

최대 합 바이 토닉 서브 어레이

Size of array = 7

Array = {1 2 5 4 10 20 1}
25

설명 : 가능한 두 개의 비트 배열이 있습니다. 하나의 서브 어레이는 {1 2 5 4}이고 다른 하나는 {4 10 20 1}입니다. 최대 합이 필요하므로 두 번째 하위 배열을 선택합니다. 그리고 우리의 답은 4 + 10 + 20 + 1 = 25입니다.

 

Size of array = 4

Array = { 100 200 300 10}
610

설명 : 전체 배열이 우리의 조건을 만족하기 때문에. 답은 610입니다.

 

최대 합 바이 토닉 부분 배열 문제에 대한 접근 방식

순진한 접근

하위 배열의 왼쪽 및 오른쪽 경계에 두 개의 포인터를 사용할 수 있습니다. 하위 배열을 수정 한 후이 시퀀스가 ​​비트인지 여부를 확인합니다. 이것이 bitonic subarray이면 합계를 취하고 그에 따라 답변을 업데이트합니다. 이 접근 방식을 따르면 XNUMX 개의 중첩 된 루프 확실히 가능한 최선의 방법은 아닙니다.

효율적인 접근

이 문제를 선형 시간 복잡성으로 해결할 수 있습니다. 두 개의 하위 배열을 생성하면 왼쪽 (left)권리, 이는 피크가 현재 요소인지, 왼쪽 방향으로 얼마나 멀리 갈 수 있고 그 합계를 왼쪽 배열의 i 번째 인덱스에 저장할 수 있는지를 나타냅니다. 우리는 속성까지 왼쪽 방향으로 갈 수 있습니다 arr [i-1] 왼쪽 방향의 모든 요소에 대해 만족합니다. 마찬가지로 올바른 하위 배열에 대해서도 수행합니다. 이제 원래 배열을 탐색하여 현재 요소가 비트 배열의 피크 일 때 만들 수있는 비트 배열의 최대 합을 찾습니다. 각 색인에서 우리는 답변을 계속 업데이트합니다.

최대 합 비트 토닉 부분 배열을 찾는 코드

C ++ 코드

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


int main(){
    int testCases;cin>>testCases;
    while(testCases--){
    	int inputSize;cin>>inputSize;
    	long long int input[inputSize];
    	for(int i=0;i<inputSize;i++){
    		cin>>input[i];
        }
        
        long long int leftSum[inputSize], rightSum[inputSize];
        for(int i=0;i<inputSize;i++)
        	leftSum[i] = rightSum[i] = input[i];
        
        leftSum[0] = input[0];
        for(int i=1;i<inputSize;i++){
        	if(input[i-1] < input[i])
        		leftSum[i] += leftSum[i-1];
        }
        
        rightSum[inputSize-1] = input[inputSize-1];
        for(int i=inputSize-2;i>=0;i--){
        	if(input[i] > input[i+1])
        		rightSum[i] += rightSum[i+1];
        }
        
        long long int answer = LLONG_MIN;
        for(int i=0;i<inputSize;i++){
        	answer = max(answer, leftSum[i] + rightSum[i] - input[i]);
        }
        cout<<answer<<endl;
    }
    return 0;
}
2
5
1 2 5 3 10
5
10 50 10 90 10
13
110

 

자바 코드

import java.util.*;
import java.lang.*;
import java.io.*;

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();
        	long input[] = new long[inputSize];
        	for(int i=0;i<inputSize;i++){
        		input[i] = sc.nextInt();
            }
            
            long leftSum[] = new long[inputSize];
            long rightSum[] = new long[inputSize];
            for(int i=0;i<inputSize;i++) {
            	leftSum[i] = input[i];
            	rightSum[i] = input[i];
            }
            
            leftSum[0] = input[0];
            for(int i=1;i<inputSize;i++){
            	if(input[i-1] < input[i])
            		leftSum[i] += leftSum[i-1];
            }
            
            rightSum[inputSize-1] = input[inputSize-1];
            for(int i=inputSize-2;i>=0;i--){
            	if(input[i] > input[i+1])
            		rightSum[i] += rightSum[i+1];
            }
            
            long answer = Long.MIN_VALUE;
            for(int i=0;i<inputSize;i++){
            	answer = Math.max(answer, leftSum[i] + rightSum[i] - input[i]);
            }
            System.out.println(answer);
        }
    }
}
2 
5 
1 2 5 3 10 
5 
10 50 10 90 10
13
110

복잡성 분석

시간 복잡성: 의 위에)

배열을 한두 번 통과하고 중첩 루프가 없었기 때문에. 선형 시간 복잡성이 있습니다.

공간 복잡성: 의 위에)

여기서 우리는 size = inputSize의 leftSum 및 rightSum이라는 두 개의 임시 배열을 만들었습니다. 1 차원 배열이기 때문에 선형 공간 복잡성도 있습니다.

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