Trong bài toán này, chúng ta được cung cấp một mảng arr []. Nhiệm vụ của chúng tôi là tạo một chương trình để tính toán Tích số tối đa của các chỉ mục lớn hơn tiếp theo ở bên trái và bên phải.
Mô tả sự cố -
Đối với mảng đã cho, chúng ta cần tìm tích của giá trị lớn nhất của left [i] * right [i]. Cả hai mảng được định nghĩa là -
left[i] = j, such that arr[i] <’. ‘ arr[j] and i > j. right[i] = j, such that arr[i] < arr[j] and i < j. *The array is 1 indexed.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[6] = {5, 2, 3, 1, 8, 6} Đầu ra
15
Giải thích
Creating left array,
left[] = {0, 1, 1, 3, 0, 5}
right[] = {5, 3, 5, 5, 0, 0}
Index products :
1 −> 0*5 = 0
2 −> 1*3 = 3
3 −> 1*5 = 5
4 −> 3*5 = 15
5 −> 0*0 = 0
6 −> 0*5 = 0 Sản phẩm tối đa
15
Phương pháp tiếp cận giải pháp -
Để tìm tích số lớn nhất của chỉ số của một phần tử lớn hơn ở bên trái và bên phải của phần tử. Trước tiên, chúng tôi sẽ tìm các chỉ số lớn hơn bên trái và bên phải và lưu trữ sản phẩm của họ để so sánh.
Bây giờ, để tìm phần tử lớn nhất của bên trái và bên phải, chúng ta sẽ lần lượt kiểm tra các phần tử lớn hơn trong giá trị chỉ mục ở bên trái và bên phải. Để tìm, chúng tôi sẽ sử dụng ngăn xếp. Và thực hiện các thao tác sau,
If stack is empty −> push current index, tos = 1. Tos is top of the stack Else if arr[i] > arr[tos] −> tos = 1.
Bằng cách sử dụng này, chúng tôi có thể tìm thấy các giá trị chỉ mục của tất cả các phần tử lớn hơn lợi nhuận bên trái và bên phải của mảng.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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<<"The maximum product of indexes of next greater on left and
right is "<<calcMaxGreaterIndedxProd(arr, n);
return 0;
} Đầu ra
The maximum product of indexes of next greater on left and right is 15