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

ปัญหา

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

Bi-tonic เซิร์บซีเควลคือลำดับพิเศษที่สมาชิกเพิ่มขึ้นก่อน แล้วตามด้วยการลดลง

ตัวอย่าง

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

อินพุต

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

เอาต์พุต

33

คำอธิบาย

เซิร์บซีเควลไบโทนิกที่ให้ผลรวมมากที่สุดคือ {2, 3, 7, 9, 6, 5, 1} ผลรวม = 2 + 3 + 7 + 9 + 6 + 5 + 1 = 33

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

เพื่อหาผลรวมสูงสุดของเซิร์บซีเควลไบโทนิก เราจะสร้างอาร์เรย์สองอันคือ incSeq[] และ decSeq[] โดยที่สำหรับสมาชิก i ที่ดัชนี incSeq[i] จะมีผลรวมของสมาชิกทั้งหมดจาก arr[0...i] ที่เพิ่มขึ้นอย่างเคร่งครัด และ decSeq[i] จะมีผลรวมของสมาชิกทั้งหมดจาก arr[i...n] ที่ลดลงอย่างเคร่งครัด

ในที่สุด เราจะคืนค่า maxSum เป็นค่าสูงสุดจาก (incSeq[i] + decSeq[i] - arr[i])

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

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

#include <iostream> 
using namespace std; 

int calcMaxVal(int a, int b){ 
    if(a > b) 
        return a; 
    return b; 
} 

int findMaxSumBiTonicSubSeq(int arr[], int N){ 
    int maxSum = -1; 
    int incSeq[N], decSeq[N]; 
    for (int i = 0; i < N; i++){ 
        decSeq[i] = arr[i]; 
        incSeq[i] = arr[i]; 
    } 
    for (int i = 1; i < N; i++) 
        for (int j = 0; j < i; j++) 
            if (arr[i] > arr[j] && incSeq[i] < incSeq[j] + arr[i]) incSeq[i] = incSeq[j] + arr[i]; 
    for (int i = N - 2; i >= 0; i--) 
        for (int j = N - 1; j > i; j--) 
            if (arr[i] > arr[j] && decSeq[i] < decSeq[j] + arr[i]) 
                decSeq[i] = decSeq[j] + arr[i]; 
    for (int i = 0; i < N; i++) 
        maxSum = calcMaxVal(maxSum, (decSeq[i] + incSeq[i] - arr[i])); 
    return maxSum; 
} 

int main(){ 
    int arr[] = {4, 2, 3, 7, 9, 6, 3, 5, 1}; 
    int N = sizeof(arr) / sizeof(arr[0]); 
    cout<<"The Maximum Sum of Bi-tonic subsequence is : "<<findMaxSumBiTonicSubSeq(arr, N); 
    return 0; 
}

เอาต์พุต

The Maximum Sum of Bi-tonic subsequence is : 33