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

Narendra Kumar

更新于：2019-12-20

347 次浏览

开启你的 职业生涯

完成课程，获得认证

入门