ผลคูณสูงสุดของทริปเปิล (ลำดับย่อยขนาด 3) ในอาร์เรย์ในโปรแกรม C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ที่ประกอบด้วยจำนวนเต็ม n ตัว ภารกิจของเราคือหาผลคูณสูงสุดของทริปเปิล (ลำดับย่อยขนาด 3) ในอาร์เรย์ ที่นี่ เราจะหาทริปเปิลที่ให้ค่าผลคูณสูงสุดขององค์ประกอบทั้งหมดของอาร์เรย์ แล้วคืนค่าผลคูณ

ตัวอย่าง

อินพุต

arr[] = {9, 5, 2, 11, 7, 4}

เอาต์พุต

693

คำอธิบาย

ที่นี่ เราจะหาทริปเปิลที่ให้ผลคูณสูงสุดขององค์ประกอบทั้งหมดของอาร์เรย์ maxProd = 9 * 11 * 7 = 693

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

สามารถมีหลายวิธีแก้ปัญหาได้ เราจะอภิปรายที่นี่

วิธีที่ 1: วิธีตรง (Brute Force)

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

อัลกอริทึม

เริ่มต้น

maxProd = -1000

ขั้นตอนที่ 1:

สร้าง 3 ลูปซ้อน: 
Loop 1: i → 0 ถึง n-3 
Loop 2: j → i ถึง n-2 
Loop 3: k → j ถึง n-1

ขั้นตอนที่ 1.1

หาผลคูณ, prod = arr[i]*arr[j]*arr[k]

ขั้นตอนที่ 1.2

ถ้า prod > maxProd → maxProd = prod

ขั้นตอนที่ 3

คืนค่า maxProd

ตัวอย่างโค้ด (วิธีที่ 1)

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

#include <iostream> 
using namespace std; 

int calcMaxProd(int arr[], int n){ 
    int maxProd = -1000; 
    int prod; 
    for (int i = 0; i < n - 2; i++) 
        for (int j = i + 1; j < n - 1; j++) 
            for (int k = j + 1; k < n; k++){ 
                prod = arr[i] * arr[j] * arr[k]; 
                if(maxProd < prod) 
                    maxProd = prod; 
            } 
    return maxProd; 
} 

int main(){ 
    int arr[] = { 9, 5, 2, 11, 7, 4 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout << "Maximum product of a triplet in array is " << calcMaxProd(arr, n); 
    return 0; 
}

เอาต์พุต

Maximum product of a triplet in array is 693

วิธีที่ 2: ใช้การเรียงลำดับ (Sorting)

ในวิธีนี้ เราจะเรียงอาร์เรย์ตามลำดับจากมากไปน้อย ในอาร์เรย์ที่เรียงแล้ว ทริปเปิลผลคูณสูงสุดจะอยู่ที่

(arr[0], arr[1], arr[2]) 
(arr[0], arr[n-1], arr[n-2])

เราจะคืนค่าสูงสุดของผลคูณของทริปเปิลเหล่านี้

อัลกอริทึม

ขั้นตอนที่ 1

เรียงอาร์เรย์ที่กำหนดตามลำดับจากมากไปน้อย

ขั้นตอนที่ 2

หาผลคูณของทริปเปิล 
maxTriplet1 = arr[0]*arr[1]*arr[2] 
maxTriplet2 = arr[0]*arr[n-1]*arr[n-2]

ขั้นตอนที่ 3

ถ้า (maxTriplet1 > maxTriplet2) → คืนค่า maxTriplet1

ขั้นตอนที่ 4

มิฉะนั้น → คืนค่า maxTriplet2

ตัวอย่างโค้ด (วิธีที่ 2)

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

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

int calcMaxProd(int arr[], int n){ 
    sort(arr, arr + n, greater<>()); 
    int maxTriplet1 = arr[0]*arr[1]*arr[2]; 
    int maxTriplet2 = arr[0]*arr[n-1]*arr[n-2]; 
    if(maxTriplet1 > maxTriplet2) 
        return maxTriplet1; 
    return maxTriplet2; 
} 

int main(){ 
    int arr[] = { 9, 5, 2, 11, 7, 4 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout << "Maximum product of a triplet in array is " << calcMaxProd(arr, n); 
    return 0; 
}

เอาต์พุต

Maximum product of a triplet in array is 693

วิธีที่ 3: หาค่าทริปเปิลโดยตรง

เนื่องจากเราทราบแล้วว่าทริปเปิลผลคูณสูงสุดสามารถมาจากทริปเปิลใดทริปเปิลหนึ่งของสองทริปเปิลนี้

(สูงสุด, สองมากสุด, สามมากสุด) 
(สูงสุด, ต่ำสุด, สองต่ำสุด)

ดังนั้น เราสามารถหาค่าเหล่านี้โดยตรงโดยการเดินทางผ่านอาร์เรย์ และใช้ค่าเหล่านี้เพื่อหาทริปเปิลผลคูณสูงสุด

อัลกอริทึม

เริ่มต้น

max = -1000, secMax = -1000, thirdMax = -1000, min = 10000, secMin = 10000

ขั้นตอนที่ 1

วนลูปอาร์เรย์ i → 0 ถึง n-1

ขั้นตอนที่ 1.1

ถ้า (arr[i] > max) → thirdMax = secMax, secMax = max, max = arr[i]

ขั้นตอนที่ 1.2

ถ้า (arr[i] > secMax) → thirdMax = secMax, secMax = arr[i]

ขั้นตอนที่ 1.3

ถ้า (arr[i] > thirdMax) → thirdMax = arr[i]

ขั้นตอนที่ 1.4

ถ้า (arr[i] < min) → secMin = min, min = arr[i]

ขั้นตอนที่ 1.5

ถ้า (arr[i] < secMin) → secMin = arr[i]

ขั้นตอนที่ 2

triplet1 = max * secMax * thirdMax 
triplet2 = max * min * secMin

ขั้นตอนที่ 3

ถ้า (triplet1 > triplet2) → คืนค่า triplet1

ขั้นตอนที่ 4

มิฉะนั้น → คืนค่า triplet2

ตัวอย่างโค้ด (วิธีที่ 3)

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

#include <iostream> 
using namespace std; 

int calcMaxProd(int arr[], int n){ 
    int max = -1000, secMax = -1000, thirdMax = -1000; 
    int min = 1000, secMin = 1000; 
    for (int i = 0; i < n; i++){ 
        if (arr[i] > max){ 
            thirdMax = secMax; 
            secMax = max; 
            max = arr[i]; 
        } 
        else if (arr[i] > secMax){ 
            thirdMax = secMax; 
            secMax = arr[i]; 
        } 
        else if (arr[i] > thirdMax) 
            thirdMax = arr[i]; 
        if (arr[i] < min){ 
            secMin = min; 
            min = arr[i]; 
        } 
        else if(arr[i] < secMin) 
            secMin = arr[i]; 
    } 
    int triplet1 = max * secMax * thirdMax; 
    int triplet2 = max * secMin * min; 
    if(triplet1 > triplet2) 
        return triplet1; 
    return triplet2; 
} 

int main(){ 
    int arr[] = { 9, 5, 2, 11, 7, 4 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout << "Maximum product of a triplet in array is " << calcMaxProd(arr, n); 
    return 0; 
}

เอาต์พุต

Maximum product of a triplet in array is 693