Tìm tổng lớn nhất của phần tử nhỏ nhất và nhỏ nhì trong mảng bằng C++

Trong bài toán này, chúng ta được cung cấp một mảng arr[]. Nhiệm vụ là viết chương trình tìm tổng lớn nhất của phần tử nhỏ nhất và nhỏ nhì trong một mảng con.

Mô tả bài toán

Chúng ta cần tìm tổng của phần tử nhỏ nhất và nhỏ nhì của mọi mảng con có thể tạo thành từ mảng gốc. Sau đó trả về tổng lớn nhất trong số đó.

Ví dụ minh họa

Đầu vào

arr[] = {3, 5, 4, 2, 9, 1, 6}

Đầu ra

11

Giải thích

Trong tất cả các mảng con có thể, {2, 9} có tổng lớn nhất của hai phần tử nhỏ nhất.
Tổng = 2 + 9 = 11

Phương pháp giải

Cách đơn giản: sinh ra tất cả các mảng con, tìm phần tử nhỏ nhất và nhỏ nhì, tính tổng, trả về tổng lớn nhất.

Cách hiệu quả hơn dựa trên quan sát: Tổng lớn nhất sẽ là tổng của một cặp hai phần tử liên tiếp trong mảng. Chúng ta chỉ cần tìm cặp phần tử liên tiếp có tổng lớn nhất.

Thuật toán

Khởi tạo

maxSum = -1

Bước 1

Vòng lặp i từ 0 đến n-2

Bước 1.1

Nếu maxSum < (arr[i] + arr[i+1]) thì maxSum = (arr[i] + arr[i+1])

Bước 2

Trả về maxSum.

Chương trình minh họa

#include <iostream>
using namespace std;

int calcMaxSumPairs(int arr[], int n) {
    int maxSum = -1;
    for (int i = 0; i < (n - 1); i++)
        if (maxSum < (arr[i] + arr[i + 1]))
            maxSum = (arr[i] + arr[i + 1]);
    return maxSum;
}

int main() {
    int arr[] = {3, 4, 2, 9, 5, 6};
    int n = sizeof(arr) / sizeof(int);
    cout << "Tổng lớn nhất của phần tử nhỏ nhất và nhỏ nhì trong mảng là "
         << calcMaxSumPairs(arr, n);
    return 0;
}

Đầu ra

Tổng lớn nhất của phần tử nhỏ nhất và nhỏ nhì trong mảng là 14