Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++의 최대 및 최소 제품 하위 집합

<시간/>

크기가 N인 정수 배열이 제공됩니다. 여기서 목표는 최대 및 최소 제품 하위 집합을 찾는 것입니다. 지금까지 발견된 최소 제품 minProd와 지금까지 발견된 최대 제품 maxProd에 대한 두 개의 제품 변수를 사용하여 이를 수행합니다.

배열을 탐색하는 동안 각 요소에 minProd와 maxProd를 곱합니다. 또한 이전 최대 제품, 이전 최소 제품, 현재 최대 제품, 현재 최소 제품 및 현재 요소 자체를 확인하십시오.

입력

Arr[]= { 1,2,5,0,2 }

출력

Maximum Product: 20
Minimum Product: 0

설명 − maxProd 및 minProd 값이 1로 초기화된 배열의 두 번째 요소부터 시작(첫 번째 요소).

Arr[1]: 1*2=2, 1*2=2, maxProd=2, minProd=1
Arr[2]: 2*5=10, 1*5=5, maxProd=10, minProd=1
Arr[3]: 10*0=0, 1*0=0, maxProd=10, minProd=0
Arr[4]: 10*2=20, 0*2=0, maxProd=20, minProd=0

입력

Arr[]= { -1,2,-5,0,2 }

출력

Maximum Product: 20
Minimum Product: -20

설명 − 최대 제품의 경우 하위 집합에는 { -1,2,-5,2 }

요소가 있습니다.

최소 제품의 경우 하위 집합에는 { 2,-5,2 }

요소가 있습니다.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

  • 정수 배열 Arr[]에는 양수 및 음수 정수가 포함됩니다.

  • 가변 크기는 배열의 길이를 포함합니다.

  • getProductSubset(int arr[], int n) 함수는 배열을 입력으로 사용하고 얻은 요소의 최대 및 최소 곱을 반환합니다.

  • 변수 curMin, curMax는 발견된 현재 최대 및 최소 제품을 저장하는 데 사용됩니다. 처음에는 [0].

  • 변수 prevMin, prevMax는 발견된 이전 최대 및 최소 제품을 저장하는 데 사용됩니다. 처음에는 [0].

  • 변수 maxProd 및 minProd는 얻은 최종 최대 및 최소 제품을 저장하는 데 사용됩니다.

  • 두 번째 요소인 arr[1]에서 마지막 인덱스까지 배열 탐색을 시작합니다.

  • 최대 곱의 경우 현재 arr[i]에 prevMax 및 prevMin을 곱합니다. 최대 제품을 curMax에 저장합니다. 이 curMax>prevMax인 경우 curMax를 prevMax로 업데이트합니다.

  • curMax>maxProd

    인 경우 curMax를 사용하여 maxProd를 업데이트합니다.
  • 마지막으로 다음 반복을 위해 prevMax를 curMax로 업데이트했습니다.

  • 비교를 변경하여 prevMin, curMin 및 minProd에 대해 위와 동일한 단계를 수행합니다.

  • 루프가 종료된 후 maxProd 및 minProd에서 얻은 결과를 인쇄합니다.

예시

#include <iostream>
using namespace std;
void getProductSubset(int arr[], int n){
   // Initialize all products with arr[0]
   int curMax = arr[0];
   int curMin = arr[0];
   int prevMax = arr[0];
   int prevMin= arr[0];
   int maxProd = arr[0];
   int minProd = arr[0];
   int temp1=0,temp2=0,temp3=0;
   // Process all elements after arr[0]
   for (int i = 1; i < n; ++i){
      /* Current maximum product is maximum of following
      1) prevMax * current arr[i] (when arr[i] is +ve)
      2) prevMin * current arr[i] (when arr[i] is -ve)
      3) current arr[i]
      4) Previous max product */
      temp1=prevMax*arr[i];
      temp2=prevMin*arr[i];
      temp3=temp1>temp2?temp1:temp2;
      curMax = temp3>arr[i]?temp3:arr[i];
      curMax = curMax>prevMax?curMax:prevMax;
      /* Current minimum product is minimum of following
      1) prevMin * current arr[i] (when arr[i] is +ve)
      2) prevMax * current arr[i] (when arr[i] is -ve)
      3) current arr[i]
      4) Previous min product */
      temp1=prevMax*arr[i];
      temp2=prevMin*arr[i];
      temp3=temp1<temp2?temp1:temp2;
      curMin = temp3<arr[i]?temp3:arr[i];
      curMin = curMin<prevMin?curMin:prevMin;
      maxProd = maxProd>curMax?maxProd:curMax;
      minProd = minProd<curMin?minProd:curMin;
      // copy current values to previous values
      prevMax = curMax;
      prevMin = curMin;
   }
   std::cout<<"Maximum Subset Product: "<<maxProd;
   std::cout<<"\nMinimum Subset Product: "<<minProd;
}
int main(){
   int Arr[] = {-4, -3, 1, 2, 0, 8, 1};
   // int arr[] = {-4, 1,1, 3, 5,7};
   int size = 7;
   getProductSubset(Arr,size ) ;
   return 0;
}

출력

Maximum Subset Product: 192
Minimum Subset Product: -64