सरणी दी गई है। किसी भी लंबाई के बढ़ते उपअनुक्रम का अधिकतम गुणनफल खोजें।
DP दृष्टिकोण: mpis[i] = इंडेक्स i पर समाप्त होने वाले बढ़ते उपअनुक्रम का अधिकतम गुणनफल।
उदाहरण: {3, 100, 4, 5, 150, 6} → अधिकतम गुणनफल 45000 (3, 100, 150)।
C++ कार्यान्वयन
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
ll lis(ll arr[], ll n) {
ll mpis[n];
for (int i = 0; i < n; i++) mpis[i] = arr[i];
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (arr[i] > arr[j] && mpis[i] < mpis[j] * arr[i])
mpis[i] = mpis[j] * arr[i];
return *max_element(mpis, mpis + n);
}
int main() {
ll arr[] = {3, 100, 4, 5, 150, 6};
ll n = sizeof(arr) / sizeof(arr[0]);
printf("%lld", lis(arr, n));
return 0;
}
आउटपुट
45000