시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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) 여기서는 보조 공간을 사용하지 않기 때문입니다.
