Tìm tổng lớn nhất các phần tử tăng dần từ n mảng trong C++

Trong bài toán này, chúng ta được cung cấp một ma trận 2-D kích thước n x m. Nhiệm vụ là viết chương trình tìm tổng lớn nhất của các phần tử theo thứ tự tăng dần từ n mảng.

Mô tả bài toán

Chúng ta cần tìm tổng lớn nhất của các phần tử bằng cách lấy một phần tử từ mỗi hàng sao cho phần tử từ hàng i nhỏ hơn phần tử từ hàng i+1, và cứ thế. Nếu không có tổng nào thỏa mãn, trả về -1.

Ví dụ minh họa

Đầu vào

mat[][] = { {4, 5, 1, 3, 6},
            {5, 9, 2, 7, 12},
            {13, 1, 3, 6, 8},
            {10, 5, 7, 2, 4} }

Đầu ra

31

Giải thích

Chọn phần tử từ ma trận để tạo tổng lớn nhất: 6 + 7 + 8 + 10 = 31
6 từ mảng 1, giá trị lớn nhất.
7 từ mảng 2, chọn 12 (giá trị lớn nhất) không cho ra giải pháp.
8 từ mảng 3, chọn 13 (giá trị lớn nhất) không cho ra giải pháp.
10 từ mảng 4, giá trị lớn nhất.

Phương pháp giải

Giải pháp là chọn một phần tử từ mảng cuối cùng của mảng các mảng, sau đó đi ngược lên trên chọn phần tử lớn nhất có thể nhỏ hơn phần tử đã cho.

Một trường hợp đặc biệt: khi không có phần tử nào trong mảng i (hàng) nhỏ hơn phần tử tại mảng i+1. Tại đây, trả về -1.

Sắp xếp mảng hỗ trợ hiệu quả giải pháp. Nếu sắp xếp tăng dần, phần tử lớn nhất sẽ ở chỉ số m-1, phần tử tiếp theo nhỏ hơn. Do đó, tìm phần tử lớn nhất thỏa mãn điều kiện trở nên dễ dàng.

Thuật toán

Khởi tạo maxSum = 0, currMax

Bước 1

Sắp xếp mỗi mảng của mảng các mảng (mỗi mảng sẽ có các phần tử theo thứ tự tăng dần).

Bước 2

currMax = mat[n-1][m-1], phần tử cuối cùng của hàng cuối cùng. Cập nhật maxSum, maxSum = currMax.

Bước 3

Duyệt qua ma trận theo hàng, i = n-2 đến 0.

Bước 3.1

Tìm phần tử lớn nhất trong mat[i][] nhỏ hơn currMax tại chỉ số j.

Bước 3.2

Nếu j < 0, tức không tìm thấy giá trị. Trả về -1.

Bước 3.3

Cập nhật currMax. currMax = mat[i][j].

Bước 3.4

Cập nhật maxSum, maxSum += currMax.

Bước 4

Trả về maxSum.

Chương trình minh họa

#include <bits/stdc++.h>
#define M 5
using namespace std;

int calcMaxSumMat(int mat[][M], int n) {
    for (int i = 0; i < n; i++)
        sort(mat[i], mat[i] + M);
    
    int maxSum = mat[n - 1][M - 1];
    int currMax = mat[n - 1][M - 1];
    int j;
    
    for (int i = n - 2; i >= 0; i--) {
        for (j = M - 1; j >= 0; j--) {
            if (mat[i][j] < currMax) {
                currMax = mat[i][j];
                maxSum += currMax;
                break;
            }
        }
        if (j == -1)
            return -1;
    }
    return maxSum;
}

int main() {
    int mat[][M] = {
        {4, 5, 1, 3, 6},
        {5, 9, 2, 7, 12},
        {12, 1, 3, 6, 8},
        {10, 5, 7, 2, 4}
    };
    int n = sizeof(mat) / sizeof(mat[0]);
    cout << "Tổng lớn nhất các phần tử tăng dần từ n mảng là " << calcMaxSumMat(mat, n);
    return 0;
}

Đầu ra

Tổng lớn nhất các phần tử tăng dần từ n mảng là 31