Tổng lớn nhất chọn 1 phần tử từ mỗi mảng theo thứ tự tăng dần trong C++

Cho N mảng kích thước M. Chọn 1 phần tử từ mỗi mảng sao cho phần tử từ mảng trước < phần tử từ mảng sau. Tối ưu tổng.

Thuật toán (Tham lam từ cuối)

• Sắp xếp từng mảng tăng dần.
• Chọn phần tử lớn nhất của mảng cuối làm prev, cộng vào sum.
• Duyệt ngược các mảng trước: chọn phần tử lớn nhất < prev, cập nhật prev, cộng vào sum.
• Nếu không tìm thấy → trả về 0.

Ví dụ triển khai (C++)

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

int maximumSum(int a[][M], int n) {
    for (int i = 0; i < n; i++) sort(a[i], a[i] + M);
    int sum = a[n-1][M-1];
    int prev = a[n-1][M-1];
    for (int i = n-2; i >= 0; i--) {
        int j;
        for (j = M-1; j >= 0; j--)
            if (a[i][j] < prev) { prev = a[i][j]; sum += prev; break; }
        if (j == -1) return 0;
    }
    return sum;
}

int main() {
    int arr[][M] = {{1,7,3,4}, {4,2,5,1}, {9,5,1,8}};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maximumSum(arr, n);
    return 0;
}

Đầu ra

18