ผลคูณสูงสุดของดัชนีค่ามากกว่าซ้ายและขวาในโปรแกรม C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ภารกิจของเราคือสร้างโปรแกรมเพื่อคำนวณผลคูณสูงสุดของดัชนีค่ามากกว่าซ้ายและขวา

คำอธิบายปัญหา

สำหรับอาร์เรย์ที่กำหนด เราต้องหาผลคูณของค่าสูงสุดของ left[i]*right[i] ทั้งสองอาร์เรย์ถูกนิยามว่า -

left[i] = j, โดยที่ arr[i] < arr[j] และ i > j 
right[i] = j, โดยที่ arr[i] < arr[j] และ i < j 
*อาร์เรย์นี้เป็น 1-indexed

ตัวอย่าง

อินพุต

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

เอาต์พุต

15

คำอธิบาย

การสร้างอาร์เรย์ left, left[] = {0, 1, 1, 3, 0, 5} 
right[] = {5, 3, 5, 5, 0, 0} 
ผลคูณดัชนี: 
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

แนวทางแก้ปัญหา

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

ตอนนี้ เพื่อหาองค์ประกอบที่มากที่สุดของซ้ายและขวา เราจะตรวจสอบทีละตัวสำหรับองค์ประกอบที่มากกว่าในค่าดัชนีด้านซ้ายและขวา เพื่อหา เราจะใช้สแต็ก (stack) และทำการดำเนินการต่อไปนี้

ถ้าสแต็กว่าง → push ดัชนีปัจจุบัน, tos = 1 
Tos คือ 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