ผลรวมสูงสุดของค่าที่น้อยที่สุดและน้อยที่สุดอันดับสองในอาร์เรย์โปรแกรม C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ภารกิจของเราคือสร้างโปรแกรมเพื่อหาผลรวมสูงสุดของค่าที่น้อยที่สุดและน้อยที่สุดอันดับสองในอาร์เรย์

คำอธิบายปัญหา

เราต้องการหาผลรวมขององค์ประกอบที่น้อยที่สุดและน้อยที่สุดอันดับสองของเซิร์ฟอาร์เรย์ (subarray) ของอาร์เรย์ และคืนค่าผลรวมสูงสุดของทั้งหมด

ตัวอย่าง

อินพุต

arr[] = {3, 5, 4, 2, 9, 1, 6}

เอาต์พุต

11

คำอธิบาย

จากเซิร์ฟอาร์เรย์ทั้งหมดที่เป็นไปได้ {2, 9} มีผลรวมสูงสุดขององค์ประกอบที่น้อยที่สุด ผลรวม = 2 + 9 = 11

แนวทางแก้ปัญหา

วิธีแก้ที่ง่ายคือการสร้างเซิร์ฟอาร์เรย์ทั้งหมด หาองค์ประกอบที่น้อยที่สุดและน้อยที่สุดอันดับสอง หาผลรวม คืนค่าผลรวมสูงสุดของทั้งหมด

วิธีแก้ที่มีประสิทธิภาพมากขึ้นขึ้นอยู่กับการสังเกตจากตัวอย่าง เราต้องการหาผลรวมสูงสุดซึ่งจะเป็นผลรวมของคู่องค์ประกอบที่อยู่ติดกันในอาร์เรย์ และเราจะหาคู่ที่มีผลรวมสูงสุด

อัลกอริทึม

เริ่มต้น

maxSum = -1

ขั้นตอนที่ 1

วนลูป i → 0 ถึง n-1

ขั้นตอนที่ 1.1

ถ้า maxSum < (arr[i] + arr[i+1]) แล้ว maxSum = (arr[i] + arr[i+1])

ขั้นตอนที่ 2

คืนค่า 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