Tìm tổng lớn nhất bằng cách chọn phần tử từ hai mảng theo thứ tự trong C++

Trong bài toán này, chúng ta được cung cấp hai mảng arr1[] và arr2[], và hai số N và M.

• N cho biết số lượng phần tử được lấy từ arr1.
• M cho biết số lượng phần tử được lấy từ arr2.

Chúng ta cần chọn một trong hai phần tử arr1[i] hoặc arr2[i] tại mỗi vị trí i, sao cho tổng là lớn nhất, với điều kiện tối đa N phần tử từ arr1 và M từ arr2.

Nhiệm vụ là viết chương trình tìm tổng lớn nhất bằng cách chọn phần tử từ hai mảng theo thứ tự trong C++.

Ví dụ minh họa

Đầu vào

arr1[] = {5, 1, 6, 2, 8, 9}
arr2[] = {8, 4, 7, 9, 1, 3}
M = 3, N = 2

Đầu ra

28

Giải thích

Các phần tử được chọn:
i = 0: arr1[0] = 5, arr2[0] = 8 -> Chọn 8
i = 1: arr1[1] = 1, arr2[1] = 4 -> Chọn 4
i = 2: arr1[2] = 6, arr2[2] = 7 -> Chọn 6
i = 3: arr1[3] = 2, arr2[3] = 9 -> Chọn 2
i = 4: arr1[4] = 8, arr2[4] = 1 -> Chọn 8
maxSum = 8 + 4 + 6 + 2 + 8 = 28

Phương pháp giải

Một giải pháp là tìm phần tử lớn hơn của arr1 và arr2 tại mỗi vị trí, cho đến khi đạt giới hạn M hoặc N. Sau đó cộng tất cả các giá trị được chọn.

Thuật toán

Khởi tạo

maxSum = 0

Bước 1

Với i từ 0 đến n-1

Bước 1.1

Nếu arr1[i] > arr2[i] và N > 0 -> maxSum += arr1[i], N--

Bước 1.2

Ngược lại nếu arr1[i] <= arr2[i] và M > 0 -> maxSum += arr2[i], M--

Bước 1.3

Ngược lại nếu M > 0 -> maxSum += arr2[i], M--

Bước 1.4

Ngược lại nếu N > 0 -> maxSum += arr1[i], N--

Bước 1.5

Ngược lại trả về maxSum.

Bước 2

Trả về maxSum.

Chương trình minh họa

#include <iostream>
using namespace std;

int calcMaxSumFromArrays(int arr1[], int arr2[], int N, int M, int size1, int size2) {
    int maxSum = 0;
    for (int i = 0; i < size1; i++) {
        if (arr1[i] > arr2[i] && N > 0) {
            maxSum += arr1[i];
            N--;
        } else if (arr1[i] <= arr2[i] && M > 0) {
            maxSum += arr2[i];
            M--;
        } else if (M > 0) {
            maxSum += arr2[i];
            M--;
        } else if (N > 0) {
            maxSum += arr1[i];
            N--;
        } else
            return maxSum;
    }
    return maxSum;
}

int main() {
    int arr1[] = {5, 1, 6, 2, 8, 9};
    int arr2[] = {8, 4, 7, 9, 1, 3};
    int N = 3, M = 2;
    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    int size2 = sizeof(arr2) / sizeof(arr2[0]);
    cout << "Tổng lớn nhất chọn từ hai mảng theo thứ tự là "
         << calcMaxSumFromArrays(arr1, arr2, N, M, size1, size2);
    return 0;
}

Đầu ra

Tổng lớn nhất chọn từ hai mảng theo thứ tự là 28