ในปัญหานี้ เราได้รับอาร์เรย์ arr[] งานของเราคือสร้างโปรแกรมเพื่อคำนวณผลคูณสูงสุดของดัชนีถัดไปมากกว่าทางซ้ายและขวา
คำอธิบายปัญหา −
สำหรับอาร์เรย์ที่กำหนด เราจำเป็นต้องค้นหาผลคูณของค่าสูงสุดของ left[i]*right[i] อาร์เรย์ทั้งสองถูกกำหนดเป็น −
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.
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[6] = {5, 2, 3, 1, 8, 6}
ผลลัพธ์
15
คำอธิบาย
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
จำนวนสินค้าสูงสุด
15
แนวทางการแก้ปัญหา −
เพื่อหาผลคูณสูงสุดของดัชนีขององค์ประกอบที่มากกว่าทางด้านซ้ายและด้านขวาขององค์ประกอบ อันดับแรก เราจะพบดัชนีด้านซ้ายและขวามากกว่าและจัดเก็บผลิตภัณฑ์ไว้เพื่อเปรียบเทียบ
ตอนนี้ เพื่อค้นหาองค์ประกอบที่ยิ่งใหญ่ที่สุดของด้านซ้ายและขวา เราจะตรวจสอบองค์ประกอบที่มากขึ้นในค่าดัชนีทางซ้ายและขวาทีละรายการ ในการค้นหาเราจะใช้สแต็ก และดำเนินการดังต่อไปนี้
If stack is empty −> push current index, tos = 1. Tos is top of the stack Else if arr[i] > arr[tos] −> tos = 1.
เมื่อใช้สิ่งนี้ เราสามารถค้นหาค่าดัชนีขององค์ประกอบทั้งหมดที่มากกว่าองค์ประกอบที่กำหนดของด้านซ้ายและขวาของอาร์เรย์
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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; }
ผลลัพธ์
The maximum product of indexes of next greater on left and right is 15