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

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

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

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

ตัวอย่าง

อินพุต

arr[] = {4, 2, 3, 6, 5, 9}

เอาต์พุต

20

คำอธิบาย

ลำดับย่อยที่เพิ่มขึ้นมีผลรวมสูงสุด: {2, 3, 6, 9} = 2 + 3 + 6 + 9 = 20

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

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

ตัวอย่างโค้ด

โปรแกรมสำหรับแสดงการทำงานของวิธีแก้ปัญหาของเรา

#include <iostream> 
using namespace std; 

int retMaxVal(int x, int y){ 
    if(x > y) 
        return x; 
    return y; 
} 

int calcMaxSubSeqSum(int arr[], int n) { 
    int maxSum = 0; 
    int sumDP[n]; 
    for (int i = 0; i < n; i++ ) 
        sumDP[i] = arr[i]; 
    for (int i = 1; i < n; i++ ) 
        for (int j = 0; j < i; j++ ) 
            if ( (sumDP[i] < (sumDP[j] + arr[i])) && ( arr[i] > arr[j] ) ) 
                sumDP[i] = sumDP[j] + arr[i]; 
    for (int i = 0; i < n; i++ ) 
        maxSum = retMaxVal(sumDP[i], maxSum); 
    return maxSum; 
} 

int main() { 
    int arr[] = {4, 2, 3, 6, 5, 9}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    cout << "The maximum Sum Increasing Subsequence using DP is " << calcMaxSubSeqSum(arr, n); 
    return 0; 
}

เอาต์พุต

Sum of maximum sum increasing subsequence is 20