Tổng lớn nhất trong lưới 2 x n sao cho không có hai phần tử liền kề trong C++

Trong bài toán này, chúng ta được cung cấp một lưới chữ nhật kích thước 2 x n. Nhiệm vụ là viết chương trình tìm tổng lớn nhất trong lưới 2 x n sao cho không có hai phần tử liền kề nhau trong C++.

Mô tả vấn đề

Để tìm tổng lớn nhất, ta không được chọn các phần tử liền kề với phần tử hiện tại theo chiều dọc, ngang hoặc chéo.

Ví dụ minh họa:

Đầu vào

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

Đầu ra

13

Giải thích

Tất cả các tổng có thể:

• Bắt đầu từ rectGrid[0][0] = 3: chỉ có thể thêm 9 hoặc 1. Tổng lớn nhất = 12.
• Bắt đầu từ rectGrid[1][0] = 4: chỉ có thể thêm 9 hoặc 1. Tổng lớn nhất = 13.
• Bắt đầu từ rectGrid[0][1] = 8: không thể thêm phần tử nào. Tổng = 8.
• Bắt đầu từ rectGrid[1][1] = 1: không thể thêm phần tử nào. Tổng = 1.
• Bắt đầu từ rectGrid[0][2] = 9: chỉ có thể thêm 3 hoặc 4. Tổng lớn nhất = 13.
• Bắt đầu từ rectGrid[1][2] = 1: chỉ có thể thêm 3 hoặc 4. Tổng lớn nhất = 5.

Tổng lớn nhất tổng thể là 13.

Phương pháp giải

Bài toán tương tự như tìm tổng lớn nhất không có phần tử liền kề trong mảng 1D. Khác biệt là mảng 2D và điều kiện liền kề. Ta xem xét phần tử lớn nhất nhất có thể từ mỗi cột (có 2 hàng), chọn các phần tử xen kẽ nhau.

Ví dụ chương trình

#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;
    }
    return findMax(nextSum, currectSum);
}

int main() {
    int rectGrid[2][20] = {{3, 8, 9, 5}, {4, 1, 2, 7}};
    int N = 4;
    cout << "Tổng lớn nhất trong lưới 2 x " << N << " không có phần tử liền kề: " << calcMaxSum(rectGrid, N);
    return 0;
}

Kết quả

Tổng lớn nhất trong lưới 2 x 4 không có phần tử liền kề: 15