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

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

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

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

อินพุต

rectGrid[2][] = {{3, 8, 9, 5}, {4, 1, 2, 7}}

เอาต์พุต

13

คำอธิบาย

ผลรวมที่เป็นไปได้ทั้งหมด:

• เริ่มจาก rectGrid[0][0] = 3 สามารถบวกได้แค่ 9 หรือ 1 ผลรวมสูงสุด = 12
• เริ่มจาก rectGrid[1][0] = 4 สามารถบวกได้แค่ 9 หรือ 1 ผลรวมสูงสุด = 13
• เริ่มจาก rectGrid[0][1] = 8 ไม่สามารถบวกองค์ประกอบอื่นได้ ผลรวม = 8
• เริ่มจาก rectGrid[1][1] = 1 ไม่สามารถบวกองค์ประกอบอื่นได้ ผลรวม = 1
• เริ่มจาก rectGrid[0][2] = 9 สามารถบวกได้แค่ 3 หรือ 4 ผลรวมสูงสุด = 13
• เริ่มจาก rectGrid[1][2] = 1 สามารถบวกได้แค่ 3 หรือ 4 ผลรวมสูงสุด = 5

ผลรวมสูงสุดโดยรวมคือ 13

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

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

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

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

#include <iostream>
using namespace std;

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

int calcMaxSum(int rectGrid[2][20], int N) {
    int currectSum = 0;
    int nextSum = 0;
    int altSum;
    for (int i = 0; i < N; i++) {
        altSum = findMax(nextSum, currectSum);
        currectSum = nextSum + findMax(rectGrid[0][i], rectGrid[1][i]);
        nextSum = altSum;
    }
    int maxSum = findMax(nextSum, currectSum);
    return maxSum;
}

int main() {
    int rectGrid[2][20] = {{3, 8, 9, 5}, {4, 1, 2, 7}};
    int N = 4;
    cout << "The maximum sum in a 2 x " << N << " grid such that no two elements are adjacent is " << calcMaxSum(rectGrid, N);
    return 0;
}

ผลลัพธ์

The maximum sum in a 2 x 4 grid such that no two elements are adjacent is 15