home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Maximum product of an increasing subsequence of size 3 in C++

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

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

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

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

long long int maxProduct(int arr[], int n) {
    int smaller[n];
    smaller[0] = -1;
    set<int> S;
    for (int i = 0; i < n; i++) {
        auto j = S.insert(arr[i]);
        auto itc = j.first; --itc;
        if (itc != S.end()) smaller[i] = *itc;
        else smaller[i] = -1;
    }
    long long int result = LLONG_MIN;
    int max_right = arr[n - 1];
    for (int i = n - 2; i >= 1; i--) {
        if (arr[i] > max_right) max_right = arr[i];
        else if (smaller[i] != -1)
            result = max(1LL * smaller[i] * arr[i] * max_right, result);
    }
    return result;
}

int main() {
    int arr[] = {10, 11, 9, 5, 6, 1, 20};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxProduct(arr, n) << endl;
    return 0;
}

เอาต์พุต

2200