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