ผลรวมสูงสุดขององค์ประกอบเรียงลำดับเพิ่มขึ้นจาก n อาร์เรย์ในโปรแกรม C++

ในปัญหานี้ เราได้รับเมทริกซ์ 2 มิติขนาด n x m ภารกิจของเราคือสร้างโปรแกรมเพื่อหาผลรวมสูงสุดขององค์ประกอบเรียงลำดับเพิ่มขึ้นจาก n อาร์เรย์

คำอธิบายโปรแกรม

ที่นี่ เราต้องหาผลรวมสูงสุดขององค์ประกอบโดยการหยิบหนึ่งองค์ประกอบจากแต่ละแถว โดยที่องค์ประกอบจากแถวที่ i ต้องน้อยกว่าองค์ประกอบจากแถวที่ (i+1) และต่อไป หากไม่มีผลรวมแบบนี้ ให้คืนค่า -1 แสดงว่าไม่มีผลลัพธ์

ตัวอย่าง

อินพุต

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

เอาต์พุต

31

คำอธิบาย

การหยิบองค์ประกอบจากเมทริกซ์เพื่อสร้างผลรวมสูงสุด: 6 + 7 + 8 + 10 = 31
6 จากอาร์เรย์ 1 ค่าสูงสุด
7 จากอาร์เรย์ 2 การเลือก 12 (ค่าสูงสุด) ไม่สามารถให้คำตอบได้
8 จากอาร์เรย์ 3 การเลือก 13 (ค่าสูงสุด) ไม่สามารถให้คำตอบได้
10 จากอาร์เรย์ 4 ค่าสูงสุด

แนวทางแก้ปัญหา

วิธีแก้ปัญหาคือการเลือกองค์ประกอบจากอาร์เรย์สุดท้ายของอาร์เรย์ของอาร์เรย์ แล้วขึ้นไปหาองค์ประกอบที่ใหญ่ที่สุดแต่น้อยกว่าองค์ประกอบที่กำหนด

ในการใช้วิธีแก้ปัญหานี้ เรามีกรณีหนึ่งที่ไม่มีองค์ประกอบในอาร์เรย์ที่ i (แถว) ที่น้อยกว่าองค์ประกอบที่ (i+1) ในที่นี้เราจะคืนค่า -1

การเรียงอาร์เรย์สามารถช่วยประสิทธิภาพของวิธีแก้ปัญหาได้ หากเราเรียงตามลำดับเพิ่มขึ้น องค์ประกอบที่ใหญ่ที่สุดจะอยู่ที่ดัชนี m-1 และถัดไปจะเล็กลง ดังนั้นการหาองค์ประกอบที่ใหญ่ที่สุดที่ตรงตามเงื่อนไขจะง่ายขึ้น

อัลกอริทึม

เริ่มต้น maxSum = 0, currMax

ขั้นตอนที่ 1

เรียงอาร์เรย์แต่ละอาร์เรย์ของอาร์เรย์ของอาร์เรย์ (แต่ละอันจะมีองค์ประกอบเรียงเพิ่มขึ้น)

ขั้นตอนที่ 2

currMax = mat[n-1][m-1] องค์ประกอบสุดท้ายหรือแถวสุดท้าย อัปเดต maxSum, maxSum = currMax

ขั้นตอนที่ 3

วนลูปผ่านเมทริกซ์ตามแถว i = n-2 ถึง 0

ขั้นตอนที่ 3.1

หาองค์ประกอบสูงสุดใน mat[i][] ที่น้อยกว่า currMax ที่ดัชนี j

ขั้นตอนที่ 3.2

ถ้า j < 0 คือ ไม่พบค่า คืนค่า -1

ขั้นตอนที่ 3.3

อัปเดต currMax currMax = mat[i][j]

ขั้นตอนที่ 3.4

อัปเดต maxSum maxSum = currMax

ขั้นตอนที่ 4

คืนค่า maxSum

ตัวอย่างโค้ด

โปรแกรมสำหรับแสดงการทำงานของวิธีแก้ปัญหาของเรา

#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 0; 
    } 
    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 << "The maximum sum of increasing order elements from n arrays is " << calcMaxSumMat(mat, n); 
    return 0; 
}

เอาต์พุต

The maximum sum of increasing order elements from n arrays is 31