Tìm tích lớn nhất của dãy con tăng dần kích thước 3 trong C++

Trong bài toán này, chúng ta được cung cấp một mảng arr[] gồm n số nguyên dương. Nhiệm vụ là viết chương trình tìm Tích lớn nhất của một dãy con tăng dần kích thước 3.

Mô tả bài toán

Ở đây, ta cần tìm tích lớn nhất của 3 phần tử của mảng sao cho chúng tạo thành dãy con tăng dần và chỉ số mảng cũng tăng dần:

arr[i]*arr[j]*arr[k] là lớn nhất, arr[i] < arr[j] < arr[k] và i < j < k

Ví dụ minh họa

Đầu vào

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

Đầu ra

495

Giải thích

Các mảng con kích thước 3 thỏa mãn điều kiện:
(5, 9, 11), tích = 5*9*11 = 495
(2, 4, 7), tích = 2*4*7 = 56
Tích lớn nhất = 495

Phương pháp giải

Cách đơn giản: lặp mảng tìm tất cả mảng con 3 phần tử thỏa mãn điều kiện. Tìm tích và trả về lớn nhất.

Thuật toán

Khởi tạo

maxProd = -1000

Bước 1

Vòng lặp i từ 0 đến n-3

Bước 1.1

Vòng lặp j từ i đến n-2

Bước 1.1.1

if(arr[i] < arr[j]) -> vòng lặp k từ j đến n-1

Bước 1.1.1.1

if(arr[j] < arr[k]) -> tìm prod = arr[i]*arr[j]*arr[k]

Bước 1.1.1.2

if(maxProd < prod) -> maxProd = prod

Bước 2

Trả về maxProd.

Chương trình minh họa (Cách 1 - O(n³))

#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 << "Tích lớn nhất dãy con tăng dần kích thước 3 là " << calcMaxProd(arr, n);
    return 0;
}

Đầu ra

Tích lớn nhất dãy con tăng dần kích thước 3 là 495

Cách này dễ nhưng dùng 3 vòng lặp lồng nhau, độ phức tạp O(n³). Cách hiệu quả hơn:

Ta xét các phần tử từ chỉ số 1 đến n-2 làm phần tử giữa của bộ 3. Tìm phần tử nhỏ hơn bên trái và lớn hơn bên phải.

Phần tử nhỏ hơn arr[i] ở bên trái với chỉ số < i.
Phần tử lớn hơn arr[i] ở bên phải với chỉ số > i.

Phần tử nhỏ nhất tìm bằng cây tìm kiếm cân bằng (set), phần tử lớn nhất duyệt từ phải sang trái tìm max.

Chương trình minh họa (Cách 2 - Hiệu quả 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 << "Tích lớn nhất dãy con tăng dần kích thước 3 là " << calMaxSubSeqProd(arr, n);
    return 0;
}

Đầu ra

Tích lớn nhất dãy con tăng dần kích thước 3 là 495