धनात्मक पूर्णांकों की सरणी दी गई है। ठीक 3 तत्वों वाले बढ़ते उपअनुक्रम का अधिकतम गुणनफल खोजें।
कुशल दृष्टिकोण: प्रत्येक तत्व के लिए बाएं तरफ सबसे बड़ा छोटा तत्व (सेट का उपयोग करके) और दाएं तरफ सबसे बड़ा तत्व ट्रैक करें।
उदाहरण: {10, 11, 9, 5, 6, 1, 20} → अधिकतम गुणनफल 2200 (10, 11, 20)।
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
long long int maxProduct(int arr[], int n) {
int smaller[n];
smaller[0] = -1;
set S;
for (int i = 0; i < n; i++) {
auto j = S.insert(arr[i]);
auto itc = j.first; --itc;
if (itc != S.end()) smaller[i] = *itc;
else smaller[i] = -1;
}
long long int result = INT_MIN;
int max_right = arr[n - 1];
for (int i = n - 2; i >= 1; i--) {
if (arr[i] > max_right) max_right = arr[i];
else if (smaller[i] != -1)
result = max(1LL * smaller[i] * arr[i] * max_right, result);
}
return result;
}
int main() {
int arr[] = {10, 11, 9, 5, 6, 1, 20};
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxProduct(arr, n) << endl;
return 0;
}
आउटपुट
2200