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