Sản phẩm tối đa của một dãy con ngày càng tăng trong Chương trình C ++

Trong bài toán này, chúng ta đưa ra một mảng arr [] có kích thước n. Nhiệm vụ của chúng tôi là tìm ra sản phẩm tối ưu của một phân khúc ngày càng tăng.

Mô tả sự cố - Chúng ta cần tìm tích số tối đa của việc tăng dần dãy con với bất kỳ kích thước nào có thể từ các phần tử của mảng.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

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

Đầu ra

2160

Giải thích

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

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là sử dụng phương pháp lập trình động. Đối với điều này, chúng tôi sẽ lưu trữ dãy con tăng dần sản phẩm tối đa cho đến phần tử đã cho của mảng và sau đó lưu trữ trong một mảng.

Thuật toán

Khởi tạo -

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

Bước 1 -

Loop for i −> 0 to n−1

Bước 1.1 -

Loop for i −> 0 to i

Bước 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]

Bước 2 -

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

Bước 3 -

Loop form i −> 0 to n−1

Bước 4 -

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

Bước 5 -

return maxProd.

Ví dụ

Chương trình hiển thị việc triển khai giải pháp của chúng tôi,

#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;
}

Đầu ra

The maximum product of an increasing subsequence is 2160