Tìm tích lớn nhất của chỉ số phần tử lớn hơn bên trái và bên phải trong C++

Trong bài toán này, chúng ta được cung cấp một mảng arr[]. Nhiệm vụ là viết chương trình tính Tích lớn nhất của chỉ số phần tử lớn hơn bên trái và bên phải.

Mô tả bài toán

Đối với mảng cho trước, ta cần tìm tích lớn nhất của left[i] * right[i]. Hai mảng được định nghĩa như sau:

left[i] = j, sao cho arr[i] < arr[j] và i > j.
right[i] = j, sao cho arr[i] < arr[j] và i < j.
*Mảng đánh chỉ số từ 1.

Ví dụ minh họa

Đầu vào

arr[6] = {5, 2, 3, 1, 8, 6}

Đầu ra

15

Giải thích

Tạo mảng left: left[] = {0, 1, 1, 3, 0, 5}
right[] = {5, 3, 5, 5, 0, 0}
Tích chỉ số:
1 -> 0*5 = 0
2 -> 1*3 = 3
3 -> 1*5 = 5
4 -> 3*5 = 15
5 -> 0*0 = 0
6 -> 0*5 = 0

Tích lớn nhất = 15

Phương pháp giải

Để tìm tích lớn nhất của chỉ số phần tử lớn hơn bên trái và bên phải. Ta trước tiên tìm chỉ số của phần tử lớn hơn bên trái và bên phải, lưu tích của chúng để so sánh.

Để tìm phần tử lớn hơn bên trái và bên phải, ta kiểm tra từng phần tử. Để tìm hiệu quả, ta sử dụng ngăn xếp (stack). Thực hiện các thao tác:

Nếu stack rỗng -> push chỉ số hiện tại, tos = 1.
Ngược lại nếu arr[i] > arr[tos] -> tos = 1.

Sử dụng cách này ta có thể tìm chỉ số của tất cả phần tử lớn hơn phần tử cho trước ở bên trái và bên phải của mảng.

Chương trình minh họa

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

int* findNextGreaterIndex(int a[], int n, char ch) {
    int* greaterIndex = new int[n];
    stack<int> index;
    
    if (ch == 'R') {
        for (int i = 0; i < n; ++i) {
            while (!index.empty() && a[i] > a[index.top() - 1]) {
                int indexVal = index.top();
                index.pop();
                greaterIndex[indexVal - 1] = i + 1;
            }
            index.push(i + 1);
        }
    } else if (ch == 'L') {
        for (int i = n - 1; i >= 0; i--) {
            while (!index.empty() && a[i] > a[index.top() - 1]) {
                int indexVal = index.top();
                index.pop();
                greaterIndex[indexVal - 1] = i + 1;
            }
            index.push(i + 1);
        }
    }
    return greaterIndex;
}

int calcMaxGreaterIndedxProd(int arr[], int n) {
    int* left = findNextGreaterIndex(arr, n, 'L');
    int* right = findNextGreaterIndex(arr, n, 'R');
    int maxProd = -1000;
    int prod;
    
    for (int i = 1; i < n; i++) {
        prod = left[i] * right[i];
        if (prod > maxProd)
            maxProd = prod;
    }
    return maxProd;
}

int main() {
    int arr[] = { 5, 2, 3, 1, 8, 6 };
    int n = sizeof(arr) / sizeof(arr[1]);
    cout << "Tích lớn nhất chỉ số phần tử lớn hơn bên trái và phải là "
         << calcMaxGreaterIndedxProd(arr, n);
    return 0;
}

Đầu ra

Tích lớn nhất chỉ số phần tử lớn hơn bên trái và phải là 15