ลำดับย่อยสลับที่มีผลรวมสูงสุดในโปรแกรม C++

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

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

ตัวอย่าง

อินพุต

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

เอาต์พุต

27

คำอธิบาย

องค์ประกอบเริ่มต้น: 5, ลด: 1, เพิ่ม: 6, ลด: 2, เพิ่ม: 4, N.A. 
ที่นี่เราสามารถใช้ 4, 8, 9 เป็นองค์ประกอบสุดท้ายของลำดับย่อย 
ผลรวม = 5 + 1 + 6 + 2 + 4 + 9 = 27

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

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

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

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

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

#include <iostream> 
#include <cstring> 
using namespace std; 

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

int calcMaxSumAltSubSeq(int arr[], int n) { 
    int maxSum = -10000; 
    int maxSumDec[n]; 
    bool isInc = false; 
    memset(maxSumDec, 0, sizeof(maxSumDec)); 
    int maxSumInc[n]; 
    memset(maxSumInc, 0, sizeof(maxSumInc)); 
    maxSumDec[0] = maxSumInc[0] = arr[0]; 
    for (int i=1; i arr[i]) { 
                maxSumDec[i] = maxVal(maxSumDec[i], 
                maxSumInc[j]+arr[i]); 
                isInc = true; 
            } 
            else if (arr[j] < arr[i] && isInc) 
                maxSumInc[i] = maxVal(maxSumInc[i], 
                maxSumDec[j]+arr[i]); 
        } 
    } 
    for (int i = 0 ; i < n; i++) 
        maxSum = maxVal(maxSum, maxVal(maxSumInc[i], maxSumDec[i])); 
    return maxSum; 
} 

int main() { 
    int arr[]= {8, 2, 3, 5, 7, 9, 10}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    cout << "The maximum sum alternating subsequence starting is " << calcMaxSumAltSubSeq(arr , n); 
    return 0; 
}

เอาต์พุต

The maximum sum alternating subsequence starting is 25