ผลคูณสูงสุดของลำดับย่อยที่เพิ่มขึ้นในโปรแกรม C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n ภารกิจของเราคือหาผลคูณสูงสุดของลำดับย่อยที่เพิ่มขึ้น

คำอธิบายปัญหา

เราต้องหาผลคูณสูงสุดของลำดับย่อยที่เพิ่มขึ้นขนาดใดก็ได้ที่เป็นไปได้จากองค์ประกอบของอาร์เรย์

ตัวอย่าง

อินพุต

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

เอาต์พุต

2160

คำอธิบาย

ลำดับย่อยที่เพิ่มขึ้นทั้งหมด: 
{5,6,8,9} ผลคูณ = 2160 
{5,6,7,9} ผลคูณ = 1890 
ที่นี่ เราพิจารณาเฉพาะลำดับย่อยขนาดสูงสุด

แนวทางแก้ปัญหา

วิธีแก้ที่ง่ายคือการใช้แนวทางการเขียนโปรแกรมแบบไดนามิก (Dynamic Programming) สำหรับสิ่งนี้ เราจะเก็บผลคูณสูงสุดของลำดับย่อยที่เพิ่มขึ้นจนถึงองค์ประกอบที่กำหนดของอาร์เรย์ แล้วเก็บในอาร์เรย์

อัลกอริทึม

เริ่มต้น

prod[] ด้วยองค์ประกอบของ arr[] 
maxProd = -1000

ขั้นตอนที่ 1

วนลูป i → 0 ถึง n-1

ขั้นตอนที่ 1.1

วนลูป j → 0 ถึง i

ขั้นตอนที่ 1.1.1

ตรวจสอบว่าองค์ประกอบปัจจุบันสร้างลำดับย่อยที่เพิ่มขึ้นได้หรือไม่ 
เช่น arr[i] > arr[j] และ arr[i]*prod[j] > prod[i] → prod[i] = prod[j]*arr[i]

ขั้นตอนที่ 2

หาองค์ประกอบสูงสุดของอาร์เรย์ ตามขั้นตอนที่ 3 และ 4

ขั้นตอนที่ 3

วนลูป i → 0 ถึง n-1

ขั้นตอนที่ 4

ถ้า (prod[i] > maxProd) → maxProd = prod[i]

ขั้นตอนที่ 5

คืนค่า 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