Divide and Conquer를 사용한 최대 부분 배열 합계

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 ByteDance 시스코 Facebook 골드만 삭스 구글 JP 모건 링크드인 Microsoft 신탁 페이팔 Paytm 동네 짱
배열 분열과 정복조회수 1025

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

문제 정책

“나누기 및 정복을 사용하는 최대 하위 배열 합계”문제에서 우리는 정렬 양의 정수와 음의 정수 모두. 연속 된 부분 배열의 가장 큰 합을 찾을 프로그램을 작성하십시오.

입력 형식

정수 N을 포함하는 첫 번째 줄입니다.

N 개의 정수를 포함하는 정수 배열을 포함하는 두 번째 줄.

출력 형식

주어진 배열의 하위 배열의 최대 합을 나타내는 정수 값을 인쇄합니다.

제약

  • 1 <= N <= 10 ^ 5
  • 1 <= a [i] <= 10 ^ 5

5
-10 2 5 12 -5
19

암호알고리즘

여기서 우리는 분열과 정복 접근하다. O (nLogn) 시간에서 최대 부분 배열 합계를 찾을 수 있습니다. 다음은 Divide and Conquer 알고리즘입니다.

1. 어레이를 두 부분으로 나눕니다.

2. 왼쪽 부분 배열에 대한 최대 부분 배열 합을 재귀 적으로 찾습니다.

3. 오른쪽 부분 배열에 대한 최대 부분 배열 합을 재귀 적으로 찾습니다.

4. 중간 점을 교차하는 최대 부분 배열 합을 찾습니다.

5. 위의 세 합계 중 최대 값을 반환합니다.

라인 2와 3은 단순 재귀 호출입니다. 하위 배열이 중간 점을 교차하도록 최대 하위 배열 합계를 찾는 방법은 무엇입니까? 선형 시간에서 교차 합계를 쉽게 찾을 수 있습니다. 아이디어는 간단합니다. 중간 점에서 시작하여 중간 왼쪽의 어떤 지점에서 끝나는 최대 합계를 찾은 다음 중간 + 1에서 시작하여 중간 + 1의 오른쪽에있는 합계 지점으로 끝나는 최대 합계를 찾습니다. 마지막으로 다음을 결합합니다. 둘과 반환.

실시

Divide and Conquer를 사용한 최대 부분 배열 합계를위한 C ++ 프로그램

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

int cross_sum(int arr[], int l, int m, int h)
{
  int sum = 0;
  int left_sum = INT_MIN;
  for (int i = m; i >= l; i--) 
  {
    sum = sum + arr[i];
    if (sum > left_sum)
      left_sum = sum;
  }
  sum = 0;
  int right_sum = INT_MIN;
  for (int i = m + 1; i <= h; i++) 
  {
    sum = sum + arr[i];
    if (sum > right_sum)
      right_sum = sum;
  }
  return max(left_sum + right_sum, max(left_sum, right_sum));
}


int max_sum(int arr[], int l, int h)
{
  if(l==h)
  {
    return arr[l];
  }
  int m=(l+h)/2;
  return max(max_sum(arr, l, m), max(max_sum(arr, m + 1, h), cross_sum(arr, l, m, h)));
} 

int main()
{
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  int sum = max_sum(a,0,n-1);
  cout<<sum<<endl;
  return 0;
}

Divide and Conquer를 사용한 최대 부분 배열 합계를위한 Java 프로그램

import java.util.Scanner;
class sum
{
    public static int cross_sum(int arr[], int l, int m, int h)
    {
            int sum = 0;
            int left_sum = -1000000;
            for (int i = m; i >= l; i--) 
            {
                    sum = sum + arr[i];
                    if (sum > left_sum)
                            left_sum = sum;
            }
            sum = 0;
            int right_sum = -1000000;
            for (int i = m + 1; i <= h; i++) 
            {
                    sum = sum + arr[i];
                    if (sum > right_sum)
                            right_sum = sum;
            }
            return Math.max(left_sum + right_sum, Math.max(left_sum, right_sum));
    }
    public static int max_sum(int arr[], int l, int h) 
    {
        if(l==h)
  {
    return arr[l];
  }
  int m=(l+h)/2;
  return Math.max(max_sum(arr, l, m), Math.max(max_sum(arr, m + 1, h), cross_sum(arr, l, m, h)));
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int [n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int sum = max_sum(a,0,n-1);
        System.out.println(sum);
    }
}
7
10 5 -106 29 100 1000 -500
1129

Divide and Conquer를 사용한 최대 부분 배열 합에 대한 복잡성 분석

시간 복잡성

O (n * logn) 어디에 n 주어진 배열의 크기입니다. 여기서 우리는이 반복 관계를 생각해냅니다. t (n) = 2 * t (n / 2) + θ (n). 이 반복 관계를 풀 때 t (n)의 값을 n * logn으로 얻습니다.

공간 복잡성

O (1) 여기서는 보조 공간을 사용하지 않기 때문입니다.

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