C++ 中子陣列中“最大值 + 最小值”最小值

問題表述

給定包含 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

更新於：2019-12-20

347 次瀏覽

開啟你的 職業生涯

完成課程，獲得認證

入門
廣告