ผลรวมสูงสุดที่ไม่มีสมาชิกสองตัวติดกันใน 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

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

เพื่อแก้ปัญหา เราจะวนลูปผ่านทุกสมาชิกของอาร์เรย์ และเก็บผลรวมสองค่า: sumVar1 และ sumVar2 sumVar1 จะรวมผลรวมกับสมาชิกปัจจุบัน และ sumVar2 จะรวมผลรวมโดยไม่รวมสมาชิกปัจจุบัน

ในแต่ละรอบ เราจะอัปเดต sumVar2 เป็น max(sumVar1, sumVar2) แล้วอัปเดต sumVar1 ต่อไป ที่สิ้นสุดลูป sumVar2 จะให้ผลรวมที่ต้องการ

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

#include<iostream>
using namespace std;

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

int findMaxSumWOAdjecent(int arr[], int N) {
    int maxSum1 = arr[0];
    int maxSum2 = 0;
    int temp;
    
    for (int i = 1; i < N; i++) {
        temp = findmaximum(maxSum1, maxSum2);
        maxSum1 = maxSum2 + arr[i];
        maxSum2 = temp;
    }
    return (findmaximum(maxSum1, maxSum2));
}

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

ผลลัพธ์

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