최대 합계 증가 하위 시퀀스

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 골드 피처 블룸버그 게시물에서 ByteDance 시트릭스 코드네이션 쿠팡 이베이 Facebook 구글 IBM Microsoft 나가로 신탁 동네 짱 Yahoo
배열 이진 검색 동적 프로그래밍조회수 439

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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

접근

  1. 새로운 배열 dp를 생성합니다. 여기서 dp [i] = a [i], 여기서 0
  2. 0 <i <n에서 외부 루프를 실행합니다.
  3. i로 끝나는 a [0, i-1]의 하위 시퀀스를 증가시키는 최대 합계를 저장하는 각 i에 대해. 마지막으로, a [j]로 끝나는 최대 합으로 하위 시퀀스를 증가시킵니다. 여기서 a [j]는 현재 요소 a [i]보다 작습니다.
  4. 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 배열에 값을 저장합니다.

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