C++のサブ配列の「max+min」の最小値

問題の説明

n個の正の要素の配列が与えられた場合、サブ配列のサイズが2以上でなければならないことを前提として、サブ配列内の最大要素と最小要素の可能な最小の合計を見つける必要があります。

例

arr [] ={10、5、15、7、2、1、3}の場合、「2 + 1」を加算すると、「最大+最小」の合計は3になります。

アルゴリズム

• サブアレイに要素を追加しても、最大値と最小値の合計は増えません。
• 配列に要素を追加しても、配列の最大値が減少することはありません。より大きな要素を追加した場合にのみ増加します。したがって、長さが2のサブアレイのみを考慮することが常に最適です。
• したがって、長さ2のすべてのサブ配列を検討し、合計を比較して最小のものを取得します。

例

#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n) {
   if (n < 2) {
      return -1;
   }
   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 << "Maximum sum = " << getMaxSum(arr, n) << endl;
   return 0;
}

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

出力

Maximum sum = 3