ในปัญหานี้ เราได้รับอาร์เรย์ arr[] งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมสูงสุดของค่าที่น้อยที่สุดและน้อยที่สุดเป็นอันดับสองในอาร์เรย์
คำอธิบายปัญหา − เราจำเป็นต้องหาผลรวมขององค์ประกอบที่เล็กที่สุดและน้อยที่สุดเป็นอันดับสองของ subarray ผลรวมของอาร์เรย์ และคืนค่าสูงสุดของผลรวมของ subarray ดังกล่าวทั้งหมด
ตัวอย่าง
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {3, 5, 4, 2, 9, 1, 6} ผลลัพธ์
11
คำอธิบาย
Their out of all subarrays possible,
{2, 9} has a maximum sum of smallest elements.
Sum = 2 + 9 = 11 แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการสร้างอาร์เรย์ย่อยทั้งหมด ค้นหาองค์ประกอบที่เล็กที่สุดและอันดับสองที่เล็กที่สุด ค้นหาผลรวม คืนยอดรวมสูงสุดทั้งหมด
วิธีแก้ปัญหาที่มีประสิทธิภาพมากขึ้นอีกวิธีหนึ่งคือการสังเกตจากตัวอย่าง เราต้องการหาผลรวมสูงสุดซึ่งจะเป็นผลรวมของสองคู่องค์ประกอบที่ต่อเนื่องกันของอาร์เรย์ และเราจะหาคู่ผลรวมสูงสุด
อัลกอริทึม
เริ่มต้น −
maxSum = −1
ขั้นตอนที่ 1 −
loop i −> 0 to n−1
ขั้นตอนที่ 1.1 −
if maxSum < (arr[i] + arr[i+1]). Then, maxSum = (arr[i] + arr[i+1])
ขั้นตอนที่ 2 −
Return maxSum.
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
using namespace std;
int calcMaxSumPairs(int arr[], int n) {
int maxSum = −1;
for (int i=0; i< (n − 1); i++)
if(maxSum < (arr[i] + arr[i + 1]))
maxSum = (arr[i] + arr[i + 1]);
return maxSum;
}
int main() {
int arr[] = {3, 4, 2, 9, 5, 6};
int n = sizeof(arr) / sizeof(int);
cout<<"The maximum sum of smallest and second smallest in an
array is "<<calcMaxSumPairs(arr, n);
return 0;
} ผลลัพธ์
The maximum sum of smallest and second smallest in an array is 14
