시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
“Maximum Sum Increasing Subsequence”문제에서 우리는 정렬. 주어진 배열의 최대 하위 시퀀스의 합을 찾습니다. 즉, 하위 시퀀스의 정수가 정렬 된 순서로 있습니다.
하위 시퀀스는 순서를 변경하지 않고 일부 요소를 삭제하여 다른 시퀀스에서 파생 된 시퀀스 인 배열의 일부입니다. 이것은 아래 예에서 설명 할 수 있습니다.
예
4 18 5 17 23
45
설명 : 위의 예에서 45는 최대 합계입니다. 위의 예에는 두 개의 증가하는 하위 시퀀스 즉, {18, 17} 및 {5, 17, 23}이 있습니다. 그러나 두 번째 하위 시퀀스에는 최대 합계가 있습니다.
접근
양수의 배열이 주어집니다. 배열의 최대 합계 하위 시퀀스의 합계를 계산하여 하위 시퀀스가 증가하는 순서에 있도록해야합니다.
예- [2,5,8,3,4,6]
그러면 일부 증가하는 하위 시퀀스는 다음과 같습니다.
[2,5,8], 합계 = 15
[2,8], 합계 = 10
[5,8], 합계 = 13
[2,3,4,6], 합계 = 15
[2,5,6], 합계 = 13 등 우리가 얻는 최대 합계는 15입니다.
문제는 간단한 하위 문제로 나눌 수 있습니다. 최적의 하부 구조. 그리고 문제는 또한 겹치는 하위 문제 재귀 트리를 그리면. 문제는 최적의 하부 구조와 중첩되는 하위 문제를 가지고 있기 때문에 다음을 사용하여 문제를 해결할 수 있습니다. 동적 프로그래밍. a [0,1, …… n-1]을 배열이고 dp [i] = 인덱스 i에서 끝나는 서브 시퀀스를 증가시키는 최대 합계로, a [i]가 마지막 요소가되도록합니다.
그러면 dp [i]는 다음과 같이 쓸 수 있습니다.
dp [i] = a [i] + max (L [j]) 여기서 0
ans는 max (dp [i])가됩니다. 여기서 0
접근
- 새로운 배열 dp를 생성합니다. 여기서 dp [i] = a [i], 여기서 0
- 0 <i <n에서 외부 루프를 실행합니다.
- i로 끝나는 a [0, i-1]의 하위 시퀀스를 증가시키는 최대 합계를 저장하는 각 i에 대해. 마지막으로, a [j]로 끝나는 최대 합으로 하위 시퀀스를 증가시킵니다. 여기서 a [j]는 현재 요소 a [i]보다 작습니다.
- dp 배열에서 최대 값을 찾으십시오.
실시
최대 합계 증가 하위 시퀀스를위한 C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
int max_sum_inc_sub(vector<int> a,int n){
vector<int> dp(a);
int ans = 0;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(a[i]>a[j] && dp[i]<dp[j]+a[i]){
dp[i] = dp[j]+a[i];
}
}
ans = max(ans,dp[i]);
}
return ans;
}
int main() {
int n;
cin>>n;
vector<int> a;
for(int i=0;i<n;i++){
int x;cin>>x;
a.push_back(x);
}
int max_sum = max_sum_inc_sub(a,n);
cout<<max_sum<<endl;
return 0;
}
최대 합계 증가 하위 시퀀스를위한 Java 프로그램
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i=0;i<n;i++){
arr[i]=sc.nextInt();
}
int ans = max_sum_inc_sub(arr,n);
System.out.println(ans);
}
public static int max_sum_inc_sub(int[] a,int n){
int[] dp = new int[n];
for(int i=0;i<n;i++){
dp[i]=a[i];
}
int ans = 0;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(a[i]>a[j] && dp[i]<dp[j]+a[i]){
dp[i] = dp[j]+a[i];
}
}
ans = Math.max(ans,dp[i]);
}
return ans;
}
}
6 2 5 8 3 4 6
15
최대 합계 증가 하위 시퀀스에 대한 복잡성 분석
시간 복잡성
O (n * n) 어디에 n 주어진 배열의 크기입니다. 여기서 우리는 XNUMX 차 시간 복잡성을 유발하는 두 개의 중첩 for 루프를 실행합니다.
공간 복잡성
O (N) 1 차원 배열을 사용하기 때문입니다. 여기서 우리는 선형 dp 배열에 값을 저장합니다.
