คำชี้แจงปัญหา
จากอาร์เรย์ขององค์ประกอบที่เป็นบวก n รายการ เราจำเป็นต้องค้นหาผลรวมต่ำสุดที่เป็นไปได้ขององค์ประกอบสูงสุดและต่ำสุดในอาร์เรย์ย่อย เนื่องจากขนาดของอาร์เรย์ย่อยควรมากกว่า 2
ตัวอย่าง
ถ้า arr[] ={10, 5, 15, 7, 2, 1, 3} ผลรวมของ “สูงสุด + นาที” คือ 3 เมื่อเราเติม “2 + 1”
อัลกอริทึม
- การเพิ่มองค์ประกอบใดๆ ลงในอาร์เรย์ย่อยจะไม่เพิ่มผลรวมของค่าสูงสุดและค่าต่ำสุด
- เนื่องจากค่าสูงสุดของอาร์เรย์จะไม่ลดลงเมื่อเพิ่มองค์ประกอบลงในอาร์เรย์ จะเพิ่มขึ้นก็ต่อเมื่อเราเพิ่มองค์ประกอบที่ใหญ่ขึ้นเท่านั้น ดังนั้นจึงเป็นการดีที่สุดที่จะพิจารณาเฉพาะอาร์เรย์ย่อยที่มีความยาว 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
