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

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

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

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

arr[i]*arr[j]*arr[k] เป็นสูงสุด, arr[i] < arr[j] < arr[k] และ i < j < k

ตัวอย่าง

อินพุต

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

เอาต์พุต

495

คำอธิบาย

เซิร์ฟอาร์เรย์ขนาด 3 ทั้งหมดที่ตรงตามเงื่อนไขคือ 
(5, 9, 11), ผลคูณ = 5*9*11 = 495 
(2, 4, 7), ผลคูณ = 2*4*7 = 56 
สูงสุด = 495

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

แนวทางง่ายในการแก้ปัญหาคือการวนลูปอาร์เรย์และหาเซิร์ฟอาร์เรย์ขนาด 3 ทั้งหมดที่ตรงตามเงื่อนไขที่กำหนด

หาผลคูณขององค์ประกอบและคืนค่าสูงสุดของผลคูณทั้งหมด

อัลกอริทึม

เริ่มต้น

maxProd = -1000

ขั้นตอนที่ 1

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

ขั้นตอนที่ 1.1

วนลูป j → i ถึง n-2

ขั้นตอนที่ 1.1.1

ถ้า (arr[i] < arr[j]) → วนลูป k → j ถึง n-1

ขั้นตอนที่ 1.1.1.1

ถ้า (arr[j] < arr[k]) → หา prod = arr[i]*arr[j]*arr[k]

ขั้นตอนที่ 1.1.1.2

ถ้า (maxProd > prod) → maxProd = prod

ขั้นตอนที่ 2

คืนค่า maxProd

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

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

#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++) 
            if(arr[i] < arr[j]){ 
                for (int k = j + 1; k < n; k++){ 
                    if(arr[j] < arr[k]){ 
                        prod = arr[i] * arr[j] * arr[k]; 
                        if(maxProd < prod) 
                            maxProd = prod; 
                    } 
                } 
            } 
    return maxProd; 
} 

int main(){ 
    int arr[] = { 5, 9, 2, 11, 4, 7 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout << "The maximum product of an increasing subsequence of size 3 is " << calcMaxProd(arr, n); 
    return 0; 
}

เอาต์พุต

The maximum product of an increasing subsequence of size 3 is 495

วิธีแก้นี้ง่ายแต่ใช้ 3 ลูปซ้อน ทำให้ความซับซ้อนของเวลาเป็นออเดอร์ O(n^3) ดังนั้นมา看วิธีแก้ที่มีประสิทธิภาพมากกว่า

ในวิธีแก้นี้ เราจะหยิบองค์ประกอบของอาร์เรย์จากดัชนี 1 ถึง n-2 และจัดการมันเป็นองค์ประกอบกลางของเซิร์ฟอาร์เรย์ 3 องค์ประกอบของเรา และหาองค์ประกอบอีกสองตัวจากอาร์เรย์

องค์ประกอบที่น้อยกว่า arr[i] ในอาร์เรย์ที่มีดัชนีน้อยกว่า i 
องค์ประกอบที่มากกว่า arr[i] ในอาร์เรย์ที่มีดัชนีมากกว่า i

องค์ประกอบที่น้อยที่สุดหาได้โดยใช้ต้นไม้ค้นหาแบบทวิภาคสมดุล (self-balancing binary search tree) และสำหรับองค์ประกอบที่มากที่สุด เราจะเดินทางจากขวาไปซ้ายและหาองค์ประกอบสูงสุดทางขวา

หลังจากหาทั้งสองค่าแล้ว เราจะหาผลคูณขององค์ประกอบเซิร์ฟอาร์เรย์ และหา maxProd โดยการเปรียบเทียบทั้งหมด

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

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

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

long calMaxSubSeqProd(int arr[] , int n) { 
    int smallerLeftEle[n]; 
    smallerLeftEle[0] = -1; 
    set<int> small; 
    for (int i = 0; i < n; i++) { 
        auto it = small.insert(arr[i]); 
        auto val = it.first; 
        --val; 
        if (val != small.end()) 
            smallerLeftEle[i] = *val; 
        else 
            smallerLeftEle[i] = -1; 
    } 
    long maxProd = -10000; 
    long prod; 
    int greaterRightEle = arr[n-1]; 
    for (int i = n-2; i >= 1; i--) { 
        if (arr[i] > greaterRightEle) 
            greaterRightEle = arr[i]; 
        else if (smallerLeftEle[i] != -1){ 
            prod = smallerLeftEle[i] * arr[i] * greaterRightEle; 
            if(prod > maxProd) 
                maxProd = prod; 
        } 
    } 
    return maxProd; 
} 

int main() { 
    int arr[] = {5, 9, 2, 11, 4, 7}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    cout << "The maximum product of an increasing subsequence of size 3 is " << calMaxSubSeqProd(arr, n); 
    return 0; 
}

เอาต์พุต

The maximum product of an increasing subsequence of size 3 is 495