Tổng lớn nhất lấy một phần tử mỗi hàng của ma trận (điều kiện tăng) trong C++

Cho ma trận mat[][]. Chọn một phần tử từ mỗi hàng sao cho: phần tử hàng hiện tại > phần tử hàng trước đó (tính từ dưới lên). Tìm tổng lớn nhất. Nếu không thể → -1.

Ví dụ: mat = {{4,6,1},{2,5,7},{9,1,2}} Chọn: hàng 3: 9, hàng 2: 7 (<9), hàng 1: 6 (<7) → Tổng = 22.

Giải thuật

Duyệt từ hàng cuối lên hàng đầu:

1. Tìm số lớn nhất trong hàng cuối, cộng vào sum.
2. Sang hàng trên: tìm số lớn nhất nhỏ hơn số vừa chọn.
3. Lặp lại. Nếu không tìm thấy → trả về -1.

Ví dụ (C++)

#include <iostream>
using namespace std;
#define row 3
#define col 3

int RowMaxSum(int a[row][col]){
    int maxValLastRow = 10000;
    int maxSum = 0;
    for(int i=row-1;i>=0;i--){
        int maxNo=-1;
        for(int j=0;j<col;j++)
            if(maxValLastRow>a[i][j] && a[i][j]>maxNo) maxNo=a[i][j];
        if(maxNo==-1) return -1;
        maxValLastRow=maxNo;
        maxSum+=maxValLastRow;
    }
    return maxSum;
}

int main(){
    int a[3][3]={{4,6,1},{2,5,7},{9,1,2}};
    cout<<"The maximum sum... is "<<RowMaxSum(a);
    return 0;
}

Đầu ra

The maximum sum of elements from each row in the matrix is 22