ผลรวมทริปเล็ตสูงสุดในอาร์เรย์ใน C++

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

ลองดูตัวอย่างเพื่อทำความเข้าใจปัญหา:

อินพุต - array = {4, 6, 1, 2}

เอาต์พุต - 12

คำอธิบาย -

all triplets are :
(4, 6, 1) = 4+6+1 = 11
(4, 6, 2) = 4+6+1 = 12
(4, 1, 2) = 4+6+1 = 7
(6, 1, 2) = 4+6+1 = 9
The maximum triplet sum is 12

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

ในวิธีนี้ เราจะรันสามลูปที่จะหาผลรวมทริปเล็ตที่เป็นไปได้ทั้งหมด และถ้าผลรวมของทริปเล็ตนี้มากกว่า maxsum เราจะกำหนดผลรวมทริปเล็ตนี้เป็น maxsum

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

โปรแกรมแสดงวิธีแก้ปัญหาของเรา:

#include <iostream>
using namespace std;

int maxSum(int arr[], int n){
    int maxSum = 0;
    int i, j, k;
    for (i = 0; i < n; i++)
        for (j = i + 1; j < n; j++)
            for (k = j + 1; k < n; k++)
                if (maxSum < arr[i] + arr[j] + arr[k]) maxSum = arr[i] + arr[j] + arr[k];
    return maxSum;
}

int main(){
    int arr[] = { 3, 5, 7 ,1, 9, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The maximum triplet sum of the array is "<<maxSum(arr, n);
    return 0;
}

ผลลัพธ์

The maximum triplet sum of the array is 21

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

ตัวอย่างโค้ด (วิธีที่มีประสิทธิภาพ)

โปรแกรมแสดงวิธีแก้ปัญหา:

#include <bits/stdc++.h>
using namespace std;

int maxSum(int arr[], int n) {
    sort(arr, arr + n);
    return arr[n - 1] + arr[n - 2] + arr[n - 3];
}

int main() {
    int arr[] = { 3, 5, 9, 1, 2, 8, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The maximum triplet sum of the array is "<<maxSum(arr, n);
    return 0;
}

ผลลัพธ์

The maximum triplet sum of the array is 24