ผลรวมสูงสุดที่ไม่มีสมาชิกสองตัวติดกัน - เซต 2 ใน C++

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

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

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

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

อินพุต

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

เอาต์พุต

22

คำอธิบาย

หาผลรวมจาก index 0 แบบข้ามกัน: 5 + 3 + 9 + 5 = 22
หาผลรวมจาก index 1 แบบข้ามกัน: 1 + 7 + 2 = 10

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

ในเซตก่อนหน้า เราได้เห็นวิธีแก้หนึ่งวิธี ที่นี่เราจะเรียนรู้แนวทาง dynamic programming เพื่อแก้ปัญหา

เพื่อแก้ด้วย Dynamic Approach เราต้องสร้างอาร์เรย์ DP[] ที่เก็บผลรวมสูงสุดจนถึง index ปัจจุบัน แล้วหาผลรวมจากอาร์เรย์ dynamic นี้

DP max ปัจจุบันคือค่าสูงสุดของ dp[i+2] + arr[i] และ dp[i+1]

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

#include <iostream>
using namespace std;

int DP[100];
bool currState[100];

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

int calcMaxSumWOAdj(int arr[], int i, int n) {
    if (i >= n) return 0;
    if (currState[i]) return DP[i];
    
    currState[i] = 1;
    DP[i] = maxVal(calcMaxSumWOAdj(arr, i + 1, n), arr[i] + calcMaxSumWOAdj(arr, i + 2, n));
    return DP[i];
}

int main() {
    int arr[] = { 5, 1, 3, 7, 9, 2, 5 };
    int n = sizeof(arr) / sizeof(int);
    cout << "The maximum sum such that no two elements are adjacent is " << calcMaxSumWOAdj(arr, 0, n);
    return 0;
}

ผลลัพธ์

The maximum sum such that no two elements are adjacent is 22