ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n งานของเราคือค้นหาผลิตภัณฑ์สูงสุดของลำดับที่เพิ่มมากขึ้น
คำอธิบายปัญหา − เราจำเป็นต้องค้นหาผลคูณสูงสุดของการเพิ่มลำดับย่อยของขนาดใดๆ ที่เป็นไปได้จากองค์ประกอบของอาร์เรย์
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
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
