C++で配列の最小値と2番目に小さい値の最大合計を求める方法

本チュートリアルでは、配列内の「最小値」と「2番目に小さい値」の合計の最大値を求めるC++プログラムについて解説します。

問題の概要

整数の配列が与えられたとき、考えられるすべての部分配列(連続する要素の組み合わせ)の中から、それぞれの部分配列における最小値と2番目に小さい値の合計を計算し、その中で最も大きくなる値を見つけることが課題です。

解法のポイント

一見するとすべての部分配列を調べる必要があるように思えますが、実は隣接する2要素のペアだけを確認すれば十分です。部分配列が長くなるほど、その中の最小値や2番目に小さい値は小さくなる(または変わらない)傾向があるため、隣接ペアの合計を超えることはないからです。

つまり、この問題は「隣接する要素同士の和の最大値を求める問題」に帰着できます。

サンプルコード

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

// 最小値と2番目に小さい値の最大合計を返す関数
int pairWithMaxSum(int arr[], int N) {
    // 要素が2つ未満の場合はペアが存在しないため -1 を返す
    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;
}

出力

11

コードの解説

まず、配列の要素数が2未満の場合はペアが作れないため -1 を返します。初期値として最初の2要素の合計を設定し、その後ループで隣接する各ペアの合計を順に比較しながら最大値を更新していきます。

例として配列 {4, 3, 1, 5, 6} の場合、隣接ペアの合計はそれぞれ「4+3=7」「3+1=4」「1+5=6」「5+6=11」となり、最大値は 11 です。

このアルゴリズムの計算量は O(N) と非常に効率的で、配列を一度走査するだけで答えが得られる点が大きなメリットです。