ผลรวมสูงสุดของเซิร์บซีเควลลดลงใน C++

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

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของ N จำนวนเต็ม งานของเราคือหาผลรวมสูงสุดของเซิร์บซีเควลลดลงใน C++

เราจะหาผลรวมสูงสุดของสมาชิกจากอาร์เรย์โดยที่เซิร์บซีเควลลดลงอย่างเคร่งครัด

ตัวอย่าง

มาดูตัวอย่างเพื่อเข้าใจปัญหา

อินพุต

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

เอาต์พุต

17

คำอธิบาย

เซิร์บซีเควลลดลงที่มีผลรวมสูงสุดคือ {10, 5, 2} = 10 + 5 + 2 = 17

วิธีแก้ปัญหา

ที่นี่ เราจะใช้วิธีการไดนามิกโปรแกรมมิ่งเพื่อหาคำตอบ เราจะสร้างอาร์เรย์ maxSum[] ซึ่งจะเก็บ maxSum จนถึงดัชนี i สูตรต่อไปนี้ถูกใช้เพื่อหาค่าของอาร์เรย์

maxSum[i] = arr[i] + max(maxSum[0 ... (i-1)])

ผลรวมสูงสุดจะได้จากสมาชิกสูงสุดของอาร์เรย์ maxSum[]

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

โปรแกรมแสดงการทำงานของคำตอบของเรา

#include <iostream> 
using namespace std; 

int findMaxSumDecSubSeq(int arr[], int N){ 
    int maximumSum = 0; 
    int maxSum[N]; 
    for (int i = 0; i < N; i++) 
        maxSum[i] = arr[i]; 
    for (int i = 1; i < N; i++) 
        for (int j = 0; j < i; j++) 
            if (arr[i] < arr[j] && maxSum[i] < maxSum[j] + arr[i]) 
                maxSum[i] = maxSum[j] + arr[i]; 
    for (int i = 0; i < N; i++) 
        if (maximumSum < maxSum[i]) 
            maximumSum = maxSum[i]; 
    return maximumSum; 
} 

int main(){ 
    int arr[] = { 5, 4, 100, 3, 2, 101, 1 }; 
    int N= sizeof(arr) / sizeof(arr[0]); 
    cout<<"The maximum sum of decreasing subsequence is "<<findMaxSumDecSubSeq(arr, N); 
    return 0; 
}

เอาต์พุต

The maximum sum of decreasing subsequence is 106