โปรแกรม C++ หาค่าต่ำสุดของ "max + min" ในซับอาร์เรย์

ข้อความโจทย์

กำหนดอาร์เรย์ของ n องค์ประกอบบวก เราต้องการหาผลรวมต่ำสุดที่เป็นไปได้ของค่าสูงสุดและต่ำสุดในซับอาร์เรย์ โดยที่ขนาดของซับอาร์เรย์ควรมากกว่าหรือเท่ากับ 2

ตัวอย่าง

ถ้า arr[] = {10, 5, 15, 7, 2, 1, 3} ผลรวมของ "max + min" คือ 3 เมื่อเราบวก "2 + 1"

อัลกอริทึม

• การเพิ่มองค์ประกอบใดๆ ให้กับซับอาร์เรย์จะไม่เพิ่มผลรวมของค่าสูงสุดและต่ำสุด
• เนื่องจากค่าสูงสุดของอาร์เรย์จะไม่ลดลงเมื่อเพิ่มองค์ประกอบเข้าไปในอาร์เรย์ จะเพิ่มขึ้นก็ต่อเมื่อเราเพิ่มองค์ประกอบที่ใหญ่กว่า ดังนั้นจึงเหมาะสมที่สุดที่จะพิจารณาเฉพาะซับอาร์เรย์ที่มีความยาว 2
• ดังนั้น พิจารณาซับอาร์เรย์ทั้งหมดที่มีความยาว 2 และเปรียบเทียบผลรวมแล้วเลือกค่าต่ำสุด

ตัวอย่างโค้ด C++

#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