Tổng lớn nhất của phần tử nhỏ nhất và nhỏ thứ hai trong mảng C++

Cho mảng số nguyên. Tìm tổng lớn nhất của hai phần tử nhỏ nhất và nhỏ thứ hai trong mọi mảng con liên tiếp có độ dài ≥ 2.

Quan sát: Trong mọi mảng con, hai phần tử nhỏ nhất luôn là hai phần tử liền kề nào đó sau khi sắp xếp. Do đó chỉ cần xét các cặp liền kề trong mảng gốc.

Thuật toán

• Nếu N < 2: trả về -1.
• Khởi tạo res = arr[0] + arr[1].
• Duyệt i từ 1 đến N-2: res = max(res, arr[i] + arr[i+1]).
• Trả về res.

Ví dụ triển khai (C++)

#include <bits/stdc++.h>
using namespace std;

int pairWithMaxSum(int arr[], int N) {
    if (N < 2) return -1;
    int res = arr[0] + arr[1];
    for (int i = 1; i < N-1; i++)
        res = max(res, arr[i] + arr[i+1]);
    return res;
}

int main() {
    int arr[] = {4, 3, 1, 5, 6};
    int N = sizeof(arr) / sizeof(int);
    cout << pairWithMaxSum(arr, N) << endl;
    return 0;
}

Đầu ra

11