ผลรวมสูงสุดในอาร์เรย์วงกลมที่ไม่มีสององค์ประกอบติดกันใน C++

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

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

อาร์เรย์วงกลม (Circular Array) เป็นอาร์เรย์ประเภทพิเศษที่องค์ประกอบตัวสุดท้ายเชื่อมต่อกับองค์ประกอบตัวแรก

ตัวอย่างเพื่อความเข้าใจ:

อินพุต

cirArr[] = {4, 1, 5, 3, 2}

เอาต์พุต

9

คำอธิบาย

ลำดับย่อยวงกลมที่ให้ผลรวมสูงสุดคือ [4, 5, 2] ผลรวม = 9

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

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

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

โปรแกรมตัวอย่างสำหรับการทำงานของวิธีแก้ปัญหา:

#include <iostream>
using namespace std;

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

int calcMaxSumSubSeq(int cirArr[], int start, int end, int n) {
    int DP[n];
    int maxSum = 0;
    for (int i = start; i < (end + 1); i++) {
        DP[i] = cirArr[i];
        if (maxSum < cirArr[i])
            maxSum = cirArr[i];
    }
    for (int i = (start + 2); i < (end + 1); i++) {
        for (int j = 0; j < i - 1; j++) {
            if (DP[i] < DP[j] + cirArr[i]) {
                DP[i] = DP[j] + cirArr[i];
                if (maxSum < DP[i])
                    maxSum = DP[i];
            }
        }
    }
    return maxSum;
}

int findMaxSum(int cirArr[], int n) {
    int maxSumArray1 = calcMaxSumSubSeq(cirArr, 0, (n - 2), n);
    int maxSumArray2 = calcMaxSumSubSeq(cirArr, 1, (n - 1), n);
    int maxSum = calcMaxVal(maxSumArray1, maxSumArray2);
    return maxSum;
}

int main() {
    int cirArr[] = {4, 1, 5, 3, 2};
    int n = sizeof(cirArr) / sizeof(cirArr[0]);
    cout << "The maximum sum in circular array such that no two elements are adjacent is " << findMaxSum(cirArr, n);
    return 0;
}

ผลลัพธ์

The maximum sum in circular array such that no two elements are adjacent is 9