최대 제품 하위 배열

난이도 중급
자주 묻는 질문 아마존 Apple 블룸버그 게시물에서 Facebook 구글 Microsoft
배열 동적 프로그래밍조회수 41

최대 제품 하위 배열 문제에서 우리는 정렬 정수의 경우 가장 큰 곱을 가진 요소가 하나 이상있는 연속 된 하위 배열을 찾습니다.

Arr = [0, -1, 0, 1, 2, -3]

최대 제품 = 2

Arr = [-1, -1, -1]

최대 제품 = -1

Arr = [0, -1, 0, -2, 0]

최대 제품 = 0

배열에 양수 값만 포함됨

배열에 음이 아닌 정수만 포함 된 경우이 문제를 먼저 해결해 봅시다.

이 경우 하위 배열에 XNUMX이 없으면 양의 곱을 가질 수 있습니다. 따라서 대답은 XNUMX이없는 하위 배열의 최대 곱입니다.

예를 들어 보겠습니다.

최대 제품 하위 배열

최대 제품 하위 배열을위한 C ++ 프로그램

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n=7;
    int arr[]={10, 1, 0, 3, 9, 2, 1};
    int ans=0,curr_product=0;
    for(int i=0;i<n;i++){
        if(arr[i]==0){
            ans=max(ans,curr_product);
            curr_product=0;
        }
        else{
            curr_product=max(arr[i]*curr_product,arr[i]);
        }
    }
    ans=max(ans,curr_product);
    cout<<ans;
}
54

For Array에는 음수 값도 포함됨

이제 배열에 음수 값도 포함되어 있다면 어떨까요?

이 경우 (i-1) 번째 인덱스로 끝나는 최대 제품이 arr [i]와 곱 해져 최적의 답을 얻을 수 있는지 확인할 수 없습니다.

예 :

arr = [1-2 -3]

최대 제품 :

  • i = 0이면 1
  • i = 1은 1입니다.
  • i = 2는 6 (-2 * -3)

이 문제를 극복하기 위해 간단히 두 개의 어레이를 만들 수 있습니다.

  1. i 번째 색인에서 끝나는 최대 제품을 저장하는 하나입니다.
  2. 기타는 i 번째 인덱스로 끝나는 최소 제품을 저장합니다.

이제 배열의 모든 위치에 세 가지 옵션이 있습니다.

  1. 현재 요소에 지금까지 계산 된 최대 제품을 곱합니다.
  2. 현재 요소에 지금까지 계산 된 최소 제품을 곱합니다.
  3. 현재 요소를 최대 제품 하위의 시작 위치로 사용
    정렬.

최대 제품 하위 배열을위한 C ++ 프로그램

#include<bits/stdc++.h>
using namespace std;
int maxProduct(int n,int a[]) {
    int mini[n];       // minimum product ending with ith index
    int maxi[n];       // maximum product ending with ith index
    
    mini[0]=a[0];
    maxi[0]=a[0];
    
    int ans = a[0];
    for(int i=1;i<n;i++) 
    {
        if(a[i]>0)
        {
            maxi[i] = max(maxi[i-1]*a[i], a[i]);
            mini[i] = min(mini[i-1]*a[i], a[i]);
        }
        else
        {
            maxi[i] = max(mini[i-1]*a[i], a[i]);
            mini[i] = min(maxi[i-1]*a[i], a[i]);
        }
        ans = max(ans, maxi[i]);
    }

    return ans;
}
int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int ans =maxProduct(n,a);
    cout<<"Maximum product of a subarray in the given array is "<<ans;
}
5
-2 7 5 -2 1
Maximum product of a subarray in the given array is 140

JAVA 프로그램

import java.util.Scanner;

class Main{ 
static int maxProduct(int a[], int n) 
{ 
  int mini[] = new int[n];       // minimum product ending with ith index
    int maxi[] = new int[n];       // maximum product ending with ith index
    
    mini[0]=a[0];
    maxi[0]=a[0];
    
    int ans = a[0];
    for(int i=1;i<n;i++) 
    {
        if(a[i]>0)
        {
            maxi[i] = Math.max(maxi[i-1]*a[i], a[i]);
            mini[i] = Math.min(mini[i-1]*a[i], a[i]);
        }
        else
        {
            maxi[i] = Math.max(mini[i-1]*a[i], a[i]);
            mini[i] = Math.min(maxi[i-1]*a[i], a[i]);
        }
        ans = Math.max(ans, maxi[i]);
    }

    return ans;
} 

  public static void main(String[] args) { 
  Scanner sc = new Scanner(System.in);
    int n;
    n = sc.nextInt();	
  int a[] = new int[n]; 
  for(int i=0;i<n;i++){
      a[i] = sc.nextInt();
  }
    System.out.println("Maximum product of a subarray in the given array is "+maxProduct(a, n)); 
  } 
}
6
4 6 -2 -9 -3 1
Maximum product of a subarray in the given array is 432

최대 제품 서브 어레이를위한 복잡성 분석

시간 복잡성 : O (n) 여기서 n은 배열의 길이입니다. 배열을 한 번만 통과하면됩니다.

공간 복잡성 : O (n) 각 위치에 대한 최소 및 최대 제품을 저장하기 위해 두 개의 배열을 사용하기 때문입니다.

참조

Translate »