C++プログラムの配列の最小値と2番目に小さい値の最大合計

この問題では、配列arr[]が与えられます。私たちのタスクは、配列内の最小値と2番目に小さい値の最大合計を見つけるプログラムを作成することです。

問題の説明 −配列の合計サブ配列の最小要素と2番目に小さい要素の合計を見つける必要があります。そして、そのようなすべてのサブ配列の合計の最大値を返します。

例

問題を理解するために例を見てみましょう

入力

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

出力

11

説明

Their out of all subarrays possible,
{2, 9} has a maximum sum of smallest elements.
Sum = 2 + 9 = 11

ソリューションアプローチ

この問題の簡単な解決策は、すべてのサブ配列を生成することです。最小および2番目に小さい要素を見つけ、合計を見つけます。すべての最大合計を返します。

もう1つのより効率的な解決策は、例の観察に基づいています。配列の2つの連続する要素ペアの合計となる最大合計を見つける必要があります。そして、最大の合計ペアを見つけます。

アルゴリズム

初期化 −

maxSum = −1

ステップ1 −

loop i −> 0 to n−1

ステップ1.1 −

if maxSum < (arr[i] + arr[i+1]). Then, maxSum = (arr[i] +
arr[i+1])

ステップ2 −

Return maxSum.

例

ソリューションの動作を説明するプログラム

#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<<"The maximum sum of smallest and second smallest in an
   array is "<<calcMaxSumPairs(arr, n);
   return 0;
}

出力

The maximum sum of smallest and second smallest in an array is 14