C++で部分配列の「最大値+最小値」の合計が最小になる値を求める方法

問題の概要

n個の正の整数からなる配列が与えられたとき、サイズが2以上の部分配列の中で、「部分配列の最大値 + 最小値」の合計が最小になる値を求めるのがこの問題です。

例

たとえば、配列が arr[] = {10, 5, 15, 7, 2, 1, 3} の場合、「2 + 1」を加算したときの「最大値 + 最小値」の合計は 3 となり、これが求める最小値です。

アルゴリズム

• 部分配列に要素を追加しても、「最大値 + 最小値」の合計がより小さくなることはありません。
• 配列の最大値は、要素を追加しても決して減少しません。より大きな要素を追加した場合にのみ増加します。そのため、長さ2の部分配列だけを考えるのが常に最適です。
• したがって、隣接する2要素からなるすべての部分配列(長さ2)を調べ、その合計を比較して最小のものを採用します。

より厳密に説明すると、任意の部分配列について、その最小値の要素と隣接する要素からなるペアを考えたとき、このペアの合計は元の部分配列の「最大値 + 最小値」を超えません。つまり、答えは必ず長さ2の部分配列(隣接ペア)で達成されるため、配列を一度走査するだけで答えを求められます。

実装例(C++)

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

int getMinSum(int *arr, int n) {
    if (n < 2) {
        return -1; // サイズが2未満の場合は条件を満たさない
    }
    int result = arr[0] + arr[1];
    for (int i = 1; i + 1 < n; ++i) {
        result = min(result, arr[i] + arr[i + 1]);
    }
    return result;
}

int main() {
    int arr[] = {10, 5, 15, 7, 2, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "最小の合計 = " << getMinSum(arr, n) << endl;
    return 0;
}

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

出力

最小の合計 = 3

計算量

時間計算量:O(n) — 配列を一度走査するだけで済みます。
空間計算量:O(1) — 追加のメモリは不要です。

このように、隣接する2要素のペアに着目するだけで、効率的に答えを求めることができます。部分配列のサイズが2以上という条件があるため、要素数が2未満の場合は -1 を返して不正な入力に対応しています。