C++ 프로그램에서 증가하는 부분 수열의 최대 곱

이 문제에서는 크기가 n인 배열 arr[]이 제공됩니다. 우리의 임무는 증가하는 부분 수열의 최대 곱을 찾는 것입니다.

문제 설명 − 배열의 요소에서 가능한 모든 크기의 부분 수열 증가의 최대 곱을 찾아야 합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

arr[] = {5, 4, 6, 8, 7, 9}

출력

2160

설명

All Increasing subsequence:
{5,6,8,9}. Prod = 2160
{5,6,7,9}. Prod = 1890
Here, we have considered only max size subsequence.

솔루션 접근 방식

문제에 대한 간단한 솔루션은 동적 프로그래밍 접근 방식을 사용하는 것입니다. 이를 위해 배열의 주어진 요소까지 최대 곱 증가 부분 시퀀스를 저장한 다음 배열에 저장합니다.

알고리즘

초기화 -

prod[] with elements of arr[].
maxProd = −1000

1단계 -

Loop for i −> 0 to n−1

1.1단계 -

Loop for i −> 0 to i

1.1.1단계

Check if the current element creates an increasing
subsequence i.e. arr[i]>arr[j] and arr[i]*prod[j]> prod[i] −>
prod[i] = prod[j]*arr[i]

2단계 -

find the maximum element of the array. Following steps 3 and 4.

3단계 -

Loop form i −> 0 to n−1

4단계 -

if(prod[i] > maxProd) −> maxPord = prod[i]

5단계 -

return maxProd.

예시

우리 솔루션의 구현을 보여주는 프로그램

#include <iostream>
using namespace std;
long calcMaxProdSubSeq(long arr[], int n) {
   long maxProdSubSeq[n];
   for (int i = 0; i < n; i++)
   maxProdSubSeq[i] = arr[i];
   for (int i = 1; i < n; i++)
   for (int j = 0; j < i; j++)
   if (arr[i] > arr[j] && maxProdSubSeq[i] <
      (maxProdSubSeq[j] * arr[i]))
   maxProdSubSeq[i] = maxProdSubSeq[j] * arr[i];
   long maxProd = −1000 ;
   for(int i = 0; i < n; i++){
      if(maxProd < maxProdSubSeq[i])
         maxProd = maxProdSubSeq[i];
   }
   return maxProd;
}
int main() {
   long arr[] = {5, 4, 6, 8, 7, 9};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum product of an increasing subsequence is "<<calcMaxProdSubSeq(arr, n);
   return 0;
}

출력

The maximum product of an increasing subsequence is 2160