หาผลรวมสูงสุดจากการเลือกสมาชิกแต่ละแถวในเมทริกซ์ใน C++

โจทย์

กำหนดเมทริกซ์ mat[][] หาผลรวมสูงสุดจากการเลือก 1 ตัวจากแต่ละแถว โดยที่ตัวที่เลือกในแถวปัจจุบันต้อง > ตัวที่เลือกในแถวก่อนหน้า (จากล่างขึ้นบน)

ตัวอย่าง: mat = {{4, 6, 1}, {2, 5, 7}, {9, 1, 2}} → เลือกแถว 3: 9, แถว 2: 7 (<9), แถว 1: 6 (<7) → Sum = 22

วิธีการแก้ปัญหา (Greedy)

1. เริ่มจากแถวสุดท้าย (bottom row) หาค่าสูงสุด → เพิ่มใน sum
2. ขึ้นไปแถวก่อนหน้า หาค่าสูงสุดที่ < ค่าที่เลือกไปแล้ว
3. ทำซ้ำจนถึงแถวแรก
4. ถ้าหาไม่พบในแถวไหน → return -1

ตัวอย่างโค้ด 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 of elements from each row in the matrix is " << RowMaxSum(a);
    return 0;
}

ผลลัพธ์

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