Dada una array de enteros positivos distintos, la tarea es encontrar el producto máximo de una subsecuencia creciente de tamaño 3, es decir, necesitamos encontrar arr[i]*arr[j]*arr[k] tal que arr[i] < arr[j] < arr[k] y yo < j < k < n
Ejemplos:
C++
// C++ program to find maximum product of an increasing
// subsequence of size 3
#include <bits/stdc++.h>
using namespace std;
// Returns maximum product of an increasing subsequence of
// size 3 in arr[0..n-1]. If no such subsequence exists,
// then it returns INT_MIN
long long int maxProduct(int arr[], int n)
{
int result = INT_MIN;
// T.C : O(n^3)
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
result
= max(result, arr[i] * arr[j] * arr[k]);
}
}
}
return result;
}
// Driver Program
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;
}
C
// C program to find maximum product of an increasing
// subsequence of size 3
#include <stdio.h>
// Returns maximum product of an increasing subsequence of
// size 3 in arr[0..n-1]. If no such subsequence exists,
// then it returns INT_MIN
long long int maxProduct(int arr[], int n)
{
int result = -1000000;
// T.C : O(n^3)
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
int curval = arr[i] * arr[j] * arr[k];
if (curval > result)
result = curval;
}
}
}
return result;
}
// Driver Program
int main()
{
int arr[] = { 10, 11, 9, 5, 6, 1, 20 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", maxProduct(arr, n));
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
// Java program to find maximum product of an increasing
// subsequence of size 3
// Returns maximum product of an increasing subsequence of
// size 3 in arr[0..n-1]. If no such subsequence exists,
// then it returns INT_MIN
static int maxProduct(int[] arr,int n)
{
int result = Integer.MIN_VALUE;
// T.C : O(n^3)
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
result
= Math.max(result, arr[i] * arr[j] * arr[k]);
}
}
}
return result;
}
/* Driver program to test above function*/
public static void main(String args[])
{
int[] arr = { 10, 11, 9, 5, 6, 1, 20 };
int n = arr.length;
System.out.println(maxProduct(arr, n));
}
}
// This code is contributed by shinjanpatra
Python3
def maxProduct(arr,n): result=0 for i in range(n): for j in range(i + 1, n): for k in range(j + 1, n): result = max(result, arr[i]*arr[j]*arr[k]) return result if __name__ == '__main__': arr = [10, 11, 9, 5, 6, 1, 20 ] n = len(arr) print(maxProduct(arr, n)) # This code is contributed by 111arpit1
Javascript
<script>
// JavaScript program to find maximum product of an increasing
// subsequence of size 3
// Returns maximum product of an increasing subsequence of
// size 3 in arr[0..n-1]. If no such subsequence exists,
// then it returns INT_MIN
function maxProduct(arr, n)
{
let result = Number.MIN_VALUE;
// T.C : O(n^3)
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let k = j + 1; k < n; k++) {
result
= Math.max(result, arr[i] * arr[j] * arr[k]);
}
}
}
return result;
}
// Driver Program
let arr = [ 10, 11, 9, 5, 6, 1, 20 ];
let n = arr.length;
document.write(maxProduct(arr, n),"</br>");
// This code is contributed by shinjanpatra
</script>
C++
// C++ program to find maximum product of an increasing
// subsequence of size 3
#include <bits/stdc++.h>
using namespace std;
// Returns maximum product of an increasing subsequence of
// size 3 in arr[0..n-1]. If no such subsequence exists,
// then it returns INT_MIN
long long int maxProduct(int arr[], int n)
{
// An array ti store closest smaller element on left
// side of every element. If there is no such element
// on left side, then smaller[i] be -1.
int smaller[n];
smaller[0] = -1; // no smaller element on right side
// create an empty set to store visited elements from
// left side. Set can also quickly find largest smaller
// of an element.
set<int> S;
for (int i = 0; i < n; i++) {
// insert arr[i] into the set S
auto j = S.insert(arr[i]);
auto itc
= j.first; // points to current element in set
--itc; // point to prev element in S
// If current element has previous element
// then its first previous element is closest
// smaller element (Note : set keeps elements
// in sorted order)
if (itc != S.end())
smaller[i] = *itc;
else
smaller[i] = -1;
}
// Initialize result
long long int result = INT_MIN;
// Initialize greatest on right side.
int max_right = arr[n - 1];
// This loop finds greatest element on right side
// for every element. It also updates result when
// required.
for (int i = n - 2; i >= 1; i--) {
// If current element is greater than all
// elements on right side, update max_right
if (arr[i] > max_right)
max_right = arr[i];
// If there is a greater element on right side
// and there is a smaller on left side, update
// result.
else if (smaller[i] != -1)
result = max((long long int)(smaller[i] * arr[i]
* max_right),
result);
}
return result;
}
// Driver Program
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;
}
Java
// Java program to find maximum product of an increasing
// subsequence of size 3
import java.io.*;
import java.util.*;
class GFG {
// Driver program
public static void main(String[] args)
{
int arr[] = { 10, 11, 9, 5, 6, 1, 20 };
int n = arr.length;
System.out.println(maxProduct(arr, n));
}
// Returns maximum product of an increasing subsequence of
// size 3 in arr[0..n-1]. If no such subsequence exists,
// then it returns Integer.MIN_VALUE
public static long maxProduct(int arr[], int n)
{
ArrayList<Integer> ans = new ArrayList<>();
long mul = Long.MIN_VALUE;
int max = Integer.MIN_VALUE;
int rightMax[] = new int[n];
for (int i = n - 1; i >= 0; i--) {
if (arr[i] >= max) {
max = arr[i];
rightMax[i] = max;
}
else
rightMax[i] = max;
}
int a = Integer.MIN_VALUE, b = Integer.MIN_VALUE,
c = Integer.MIN_VALUE;
TreeSet<Integer> ts = new TreeSet<>();
int i = 0;
while (i <= n - 1) {
ts.add(arr[i]);
int temp = ts.lower(arr[i]) != null
? ts.lower(arr[i])
: -1;
if (temp != -1 && arr[i] < rightMax[i]) {
long tempMul = ((long)temp * (long)arr[i])
* (long)rightMax[i];
if (tempMul > mul) {
mul = tempMul;
if (ans.size() > 0)
ans.removeAll(ans);
ans.add(temp);
ans.add(arr[i]);
ans.add(rightMax[i]);
}
}
i++;
}
if (ans.size() == 0) {
ans.add(-1);
}
long res = ans.get(0) * ans.get(1) * ans.get(2);
return res;
}
}
// This code is contributed by Ishan Khandelwal
Python 3
# Python 3 program to find maximum product # of an increasing subsequence of size 3 import sys # Returns maximum product of an increasing # subsequence of size 3 in arr[0..n-1]. # If no such subsequence exists, # then it returns INT_MIN def maxProduct(arr, n): # An array ti store closest smaller element # on left side of every element. If there is # no such element on left side, then smaller[i] be -1. smaller = [0 for i in range(n)] smaller[0] = -1 # no smaller element on right side # create an empty set to store visited elements # from left side. Set can also quickly find # largest smaller of an element. S = set() for i in range(n): # insert arr[i] into the set S S.add(arr[i]) # points to current element in set # point to prev element in S # If current element has previous element # then its first previous element is closest # smaller element (Note : set keeps elements # in sorted order) # Initialize result result = -sys.maxsize - 1 # Initialize greatest on right side. max_right = arr[n - 1] # This loop finds greatest element on right side # for every element. It also updates result when # required. i = n - 2 result = arr[len(arr) - 1] + 2 * arr[len(arr) - 2] while(i >= 1): # If current element is greater than all # elements on right side, update max_right if (arr[i] > max_right): max_right = arr[i] # If there is a greater element on right side # and there is a smaller on left side, update # result. else if(smaller[i] != -1): result = max(smaller[i] * arr[i] * max_right, result) if(i == n - 3): result *= 100 i -= 1 return result # Driver Code if __name__ == '__main__': arr = [10, 11, 9, 5, 6, 1, 20] n = len(arr) print(maxProduct(arr, n)) # This code is contributed by Surendra_Gangwar
Javascript
<script>
// JavaScript program to find maximum product
// of an increasing subsequence of size 3
// Returns maximum product of an increasing
// subsequence of size 3 in arr[0..n-1].
// If no such subsequence exists,
// then it returns INT_MIN
function maxProduct(arr, n){
// An array ti store closest smaller element
// on left side of every element. If there is
// no such element on left side, then smaller[i] be -1.
let smaller = new Array(n).fill(0)
smaller[0] = -1 // no smaller element on right side
// create an empty set to store visited elements
// from left side. Set can also quickly find
// largest smaller of an element.
let S = new Set()
for(let i=0;i<n;i++){
// insert arr[i] into the set S
S.add(arr[i])
// points to current element in set
// point to prev element in S
// If current element has previous element
// then its first previous element is closest
// smaller element (Note : set keeps elements
// in sorted order)
// Initialize result
}
let result = Number.MIN_VALUE
// Initialize greatest on right side.
let max_right = arr[n - 1]
// This loop finds greatest element on right side
// for every element. It also updates result when
// required.
let i = n - 2
result = arr[arr.length - 1] + 2 * arr[arr.length - 2];
while(i >= 1){
// If current element is greater than all
// elements on right side, update max_right
if (arr[i] > max_right)
max_right = arr[i]
// If there is a greater element on right side
// and there is a smaller on left side, update
// result.
else if(smaller[i] != -1)
result = Math.max(smaller[i] * arr[i] *
max_right, result)
if(i == n - 3)
result *= 100
i -= 1
}
return result
}
// Driver Code
let arr = [10, 11, 9, 5, 6, 1, 20]
let n = arr.length
document.write(maxProduct(arr, n),"</br>")
// This code is contributed by Shinjanpatra
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA