증가하는 하위 시퀀스의 최대 곱

난이도 쉽게
자주 묻는 질문 수행자 GE 헬스 케어 HackerRank IBM Snapchat Yahoo
배열 동적 프로그래밍조회수 22

문제 정책

"증가하는 하위 시퀀스의 최대 곱"문제는 정수 배열이 제공된다는 것을 나타냅니다. 이제 증가하는 하위 시퀀스의 요소를 곱하여 얻을 수있는 최대 제품을 찾아야합니다. 주목할 점은 가장 오래 증가하는 하위 시퀀스를 찾아서는 안된다는 것입니다. 하위 시퀀스가 ​​더 작을 수 있지만 최대 제품이 있어야합니다.

증가하는 하위 시퀀스의 최대 곱

10, 1, 1000, 2, 3, 4
10000

증가하는 하위 시퀀스의 최대 곱은 10, 1000입니다. 가장 긴 증가하는 하위 시퀀스가 ​​{1, 2, 3, 4}이지만.

접근

문제는 다음과 유사합니다. 가장 오래 증가하는 하위 시퀀스 문제. 이 문제에 대한 약간의 수정은 가장 오래 증가하는 하위 시퀀스를 찾는 대신입니다. 증가하는 하위 시퀀스의 최대 곱을 찾아야합니다.

그래서,이 문제를 해결하기 위해. Brute Force Approach를 사용하여 문제를 해결할 수도 있습니다. 이 방법은 비효율적이지만 알고 있어야합니다. 따라서 무차별 대입 방식에서는 먼저 모든 하위 시퀀스를 생성합니다. 하위 시퀀스를 생성 한 후 checker 함수를 생성합니다. 검사기 기능에서 하위 시퀀스가 ​​유효한지 확인합니다. 검사기 기능의 유효성은 하위 시퀀스가 ​​증가하는 하위 시퀀스 여야 함을 의미합니다. 그 후, 우리는 증가하는 하위 시퀀스에서 찾은 최대 제품을 계속 업데이트합니다.

이제 문제는 어떻게 문제를 효율적으로 해결 하는가입니다. 문제를 효율적으로 해결하기 위해 동적 프로그래밍을 사용합니다. 문제의 전환은 LIS 문제의 전환과 동일합니다. DP 어레이는 현재 요소까지 모든 요소를 ​​고려하면 얻을 수있는 최대 제품을 저장합니다. 그리고 하위 시퀀스가 ​​현재 요소를 포함해야한다는 조건이 하나 더 있습니다. 그런 다음 DP 배열을 계산하기 위해 현재 요소에서 시작 요소까지 역방향으로 중첩 된 루프를 실행합니다. 현재 요소보다 작은 요소를 찾으면 현재 요소를 DP 배열의 해당 인덱스에있는 요소에 곱하는 것이 현재 저장된 값보다 큰 경우 답변을 업데이트합니다.

암호

증가하는 하위 시퀀스의 최대 곱을 찾는 C ++ 코드

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


int maxProductOfIncreasingSubsequence(vector<int> &input){
  vector<int> dp(n);
  dp[0] = input[0];
  int ans = input[0];
  for(int i=1;i<n;i++){
    for(int j=0;j<i;j++){
      if(input[j] < input[i])
        dp[i] = max(dp[i], dp[j]*input[i]);
    }
    ans = max(ans, dp[i]);
  }
  return ans;
}

int main(){
  int n;cin>>n;
  vector<int> input(n);
  for(int i=0;i<n;i++)
    cin>>input[i];

  cout<<maxProductOfIncreasingSubsequence(input);
}
6
10 1 1000 2 3 4
10000

증가하는 하위 시퀀스의 최대 제품을 찾는 Java 코드

import java.util.*;

class Main{
    static int maxProductOfIncreasingSubsequence(ArrayList<Integer> input){
    ArrayList<Integer> dp = new ArrayList<Integer>();
    dp.add(input.get(0));
    int ans = input.get(0);
    int n = input.size();
    for(int i=1;i<n;i++){
      dp.add(input.get(i));
      for(int j=0;j<i;j++){
        if(input.get(j) < input.get(i))
          dp.set(i, Math.max(dp.get(i), dp.get(j)*input.get(i)));
      }
      ans = Math.max(ans, dp.get(i));
    }
    return ans;
  }

  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    ArrayList<Integer> input = new ArrayList<>();
    for(int i=0;i<n;i++){
      int in = sc.nextInt();
      input.add(in);
    }

    int answer = maxProductOfIncreasingSubsequence(input);
    System.out.print(answer);
  }
}
6
10 1 1000 2 3 4
10000

복잡성 분석

시간 복잡성

O (N ^ 2) 두 개의 중첩 루프를 사용하기 때문입니다. 하나는 모든 요소에 걸쳐 실행되고 다른 내부 루프는 현재 요소까지 모든 요소에 걸쳐 실행됩니다.

공간 복잡성

O (N) 우리는 XNUMX 차원 DP 테이블을 생성하기 때문입니다. 따라서 공간 복잡성은 선형입니다.

Translate »