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

この問題では、整数型の配列 arr[] が与えられます。求めるのは、配列の各部分配列における「最小値と2番目に小さい値の合計」の中で最大となる値です。

問題の説明

配列から取り得るすべての部分配列（連続する要素の並び）を考えます。それぞれの部分配列について、含まれる要素のうち最も小さい値と2番目に小さい値を足し合わせ、その合計が最大になるものを答えとして返します。

入出力例

入力

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

出力

11

解説

すべての部分配列の中で、
{2, 9} のとき「最小値＋2番目に小さい値」の合計が最大になります。
合計 = 2 + 9 = 11

解法のアプローチ

素朴な解法（全探索）

最も単純な方法は、すべての部分配列を生成し、それぞれについて最小値と2番目に小さい値を求めて合計を計算し、その最大値を返すことです。ただしこの方法は計算量が O(n²) となり、配列が大きい場合には非効率です。

効率的な解法（隣接ペアに着目）

例を観察すると、重要な性質が見えてきます。答えは必ず「隣り合う2つの要素の和」の最大値と一致するのです。

理由は次の通りです。ある部分配列の最小値がインデックス i にあるとき、部分配列の長さが2以上であれば、その隣（i−1 または i+1）の要素も必ず部分配列に含まれます。この隣接要素の値は必ず「2番目に小さい値」以上であるため、隣接ペアの和は元の合計以上になります。逆に、隣接する2要素だけからなる部分配列を考えれば、その合計はまさに「最小値＋2番目に小さい値」と一致します。したがって、答えは隣接ペアの和の最大値となります。

この性質を利用すれば、配列を一度走査するだけでよく、計算量は O(n) に抑えられます。

アルゴリズム

初期化：

maxSum = -1

ステップ1：

i を 0 から n-2 までループさせる

ステップ1.1：

もし maxSum ＜ (arr[i] + arr[i+1]) ならば、
maxSum = (arr[i] + arr[i+1]) と更新する

ステップ2：

maxSum を返す

C++実装例

上記の解法を実装したプログラムがこちらです。

#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 << "配列における最小値と2番目に小さい値の最大合計は "
         << calcMaxSumPairs(arr, n);
    return 0;
}

出力

配列における最小値と2番目に小さい値の最大合計は 14

まとめ

この問題は一見するとすべての部分配列を調べる必要があるように思えますが、「答えは隣接する2要素の和の最大値に等しい」という性質を見抜くことで、O(n) の線形時間で解くことができます。なお、配列の要素数が2未満の場合は有効なペアが存在しないため、初期値の -1 がそのまま返される点にも注意しましょう。