Dada una array A[] de n enteros, la tarea es encontrar una subsecuencia de tamaño k cuyo producto sea el máximo entre todas las posibles subsecuencias de tamaño k de la array dada.
Restricciones
1 <= n <= 10^5 1 <= k <= n
Ejemplos:
Input : A[] = {1, 2, 0, 3},
k = 2
Output : 6
Explanation : Subsequence containing elements
{2, 3} gives maximum product : 2*3 = 6
Input : A[] = {1, 2, -1, -3, -6, 4},
k = 4
Output : 144
Explanation : Subsequence containing {2, -3,
-6, 4} gives maximum product : 2*(-3)*(-6)*4
= 144
A continuación se presentan diferentes casos que se presentan en este problema.
- CASO I: si el elemento máximo de A es 0 y k es impar Aquí si no incluimos 0 en la subsecuencia entonces el producto será menor que 0, ya que el producto de un número impar de números enteros negativos da un número entero negativo. Por lo tanto, 0 debe incluirse en la subsecuencia. Dado que 0 está presente en la subsecuencia, el producto de la subsecuencia es 0. Respuesta = 0.
- CASO II: si el máximo elemento de A es negativo y k es impar . Aquí el producto será menor que 0,
ya que el producto de un número impar de enteros negativos da un entero negativo. Entonces, para obtener el producto máximo, tomamos el producto de los k elementos más pequeños (valor absoluto). Desde el valor absoluto sabio: | A[n-1] | > | A[n-2] | … > | A[0] |. Por lo tanto, tomamos el producto de A[n-1], A[n-2], A[n-3], …. A[nk]
Respuesta = A[n-1] * A[n-2] * ….. * A[nk] - CASO III: si el máximo elemento de A es positivo y k es impar . Aquí, en la subsecuencia del tamaño k, si todos los elementos son <0, entonces el producto será menor que 0, ya que el producto de un número impar de números enteros negativos da un número entero negativo. Por lo tanto, al menos un elemento debe ser un entero positivo en la subsecuencia. Para obtener el producto máximo, el número positivo máximo debe estar presente en la subsecuencia. Ahora necesitamos agregar k-1 elementos más a la subsecuencia.
Como k es impar, k-1 se vuelve par. Así que el problema se reduce al caso IV. Respuesta = A[n-1] * Respuesta del CASO IV. - CASO IV: si k es par . Como k es par, siempre sumamos un par en subsecuencia. Entonces, el total de pares que se deben agregar en la subsecuencia es k/2. Por simplicidad, nuestro nuevo k es k/2. Ahora que A está ordenado, el par con el producto máximo siempre será A[0]*A[1] O A[n-1]*A[n-2]. En caso de duda sobre la afirmación anterior piensa en números negativos 🙂
Now,
if A[0]*A[1] > A[n-1]*A[n-2],
second max product pair will be
either A[2]*A[3] OR A[n-1]*[n-2].
else second max product pair will be
either A[0]*A[1] OR A[n-3]*[n-4].
Aquí está la implementación de la solución anterior.
C++
// C++ code to find maximum possible product of
// sub-sequence of size k from given array of n
// integers
#include <algorithm> // for sorting
#include <iostream>
using namespace std;
// Required function
int maxProductSubarrayOfSizeK(int A[], int n, int k)
{
// sorting given input array
sort(A, A + n);
// variable to store final product of all element
// of sub-sequence of size k
int product = 1;
// CASE I
// If max element is 0 and
// k is odd then max product will be 0
if (A[n - 1] == 0 && (k & 1))
return 0;
// CASE II
// If all elements are negative and
// k is odd then max product will be
// product of rightmost-subarray of size k
if (A[n - 1] <= 0 && (k & 1)) {
for (int i = n - 1; i >= n - k; i--)
product *= A[i];
return product;
}
// else
// i is current left pointer index
int i = 0;
// j is current right pointer index
int j = n - 1;
// CASE III
// if k is odd and rightmost element in
// sorted array is positive then it
// must come in subsequence
// Multiplying A[j] with product and
// correspondingly changing j
if (k & 1) {
product *= A[j];
j--;
k--;
}
// CASE IV
// Now k is even
// Now we deal with pairs
// Each time a pair is multiplied to product
// ie.. two elements are added to subsequence each time
// Effectively k becomes half
// Hence, k >>= 1 means k /= 2
k >>= 1;
// Now finding k corresponding pairs
// to get maximum possible value of product
for (int itr = 0; itr < k; itr++) {
// product from left pointers
int left_product = A[i] * A[i + 1];
// product from right pointers
int right_product = A[j] * A[j - 1];
// Taking the max product from two choices
// Correspondingly changing the pointer's position
if (left_product > right_product) {
product *= left_product;
i += 2;
}
else {
product *= right_product;
j -= 2;
}
}
// Finally return product
return product;
}
// Driver Code to test above function
int main()
{
int A[] = { 1, 2, -1, -3, -6, 4 };
int n = sizeof(A) / sizeof(A[0]);
int k = 4;
cout << maxProductSubarrayOfSizeK(A, n, k);
return 0;
}
Java
// Java program to find maximum possible product of
// sub-sequence of size k from given array of n
// integers
import java.io.*;
import java.util.*;
class GFG {
// Function to find maximum possible product
static int maxProductSubarrayOfSizeK(int A[], int n, int k)
{
// sorting given input array
Arrays.sort(A);
// variable to store final product of all element
// of sub-sequence of size k
int product = 1;
// CASE I
// If max element is 0 and
// k is odd then max product will be 0
if (A[n - 1] == 0 && k % 2 != 0)
return 0;
// CASE II
// If all elements are negative and
// k is odd then max product will be
// product of rightmost-subarray of size k
if (A[n - 1] <= 0 && k % 2 != 0) {
for (int i = n - 1; i >= n - k; i--)
product *= A[i];
return product;
}
// else
// i is current left pointer index
int i = 0;
// j is current right pointer index
int j = n - 1;
// CASE III
// if k is odd and rightmost element in
// sorted array is positive then it
// must come in subsequence
// Multiplying A[j] with product and
// correspondingly changing j
if (k % 2 != 0) {
product *= A[j];
j--;
k--;
}
// CASE IV
// Now k is even
// Now we deal with pairs
// Each time a pair is multiplied to product
// ie.. two elements are added to subsequence each time
// Effectively k becomes half
// Hence, k >>= 1 means k /= 2
k >>= 1;
// Now finding k corresponding pairs
// to get maximum possible value of product
for (int itr = 0; itr < k; itr++) {
// product from left pointers
int left_product = A[i] * A[i + 1];
// product from right pointers
int right_product = A[j] * A[j - 1];
// Taking the max product from two choices
// Correspondingly changing the pointer's position
if (left_product > right_product) {
product *= left_product;
i += 2;
}
else {
product *= right_product;
j -= 2;
}
}
// Finally return product
return product;
}
// driver program
public static void main(String[] args)
{
int A[] = { 1, 2, -1, -3, -6, 4 };
int n = A.length;
int k = 4;
System.out.println(maxProductSubarrayOfSizeK(A, n, k));
}
}
// Contributed by Pramod Kumar
Python 3
# Python 3 code to find maximum possible # product of sub-sequence of size k from # given array of n integers # Required function def maxProductSubarrayOfSizeK(A, n, k): # sorting given input array A.sort() # variable to store final product of # all element of sub-sequence of size k product = 1 # CASE I # If max element is 0 and # k is odd then max product will be 0 if (A[n - 1] == 0 and (k & 1)): return 0 # CASE II # If all elements are negative and # k is odd then max product will be # product of rightmost-subarray of size k if (A[n - 1] <= 0 and (k & 1)) : for i in range(n - 1, n - k + 1, -1): product *= A[i] return product # else # i is current left pointer index i = 0 # j is current right pointer index j = n - 1 # CASE III # if k is odd and rightmost element in # sorted array is positive then it # must come in subsequence # Multiplying A[j] with product and # correspondingly changing j if (k & 1): product *= A[j] j-= 1 k-=1 # CASE IV # Now k is even. So, Now we deal with pairs # Each time a pair is multiplied to product # ie.. two elements are added to subsequence # each time. Effectively k becomes half # Hence, k >>= 1 means k /= 2 k >>= 1 # Now finding k corresponding pairs to get # maximum possible value of product for itr in range( k) : # product from left pointers left_product = A[i] * A[i + 1] # product from right pointers right_product = A[j] * A[j - 1] # Taking the max product from two # choices. Correspondingly changing # the pointer's position if (left_product > right_product) : product *= left_product i += 2 else : product *= right_product j -= 2 # Finally return product return product # Driver Code if __name__ == "__main__": A = [ 1, 2, -1, -3, -6, 4 ] n = len(A) k = 4 print(maxProductSubarrayOfSizeK(A, n, k)) # This code is contributed by ita_c
C#
// C# program to find maximum possible
// product of sub-sequence of size k
// from given array of n integers
using System;
class GFG {
// Function to find maximum possible product
static int maxProductSubarrayOfSizeK(int[] A, int n,
int k)
{
// sorting given input array
Array.Sort(A);
// variable to store final product of
// all element of sub-sequence of size k
int product = 1;
int i;
// CASE I
// If max element is 0 and
// k is odd then max product will be 0
if (A[n - 1] == 0 && k % 2 != 0)
return 0;
// CASE II
// If all elements are negative and
// k is odd then max product will be
// product of rightmost-subarray of size k
if (A[n - 1] <= 0 && k % 2 != 0) {
for (i = n - 1; i >= n - k; i--)
product *= A[i];
return product;
}
// else
// i is current left pointer index
i = 0;
// j is current right pointer index
int j = n - 1;
// CASE III
// if k is odd and rightmost element in
// sorted array is positive then it
// must come in subsequence
// Multiplying A[j] with product and
// correspondingly changing j
if (k % 2 != 0) {
product *= A[j];
j--;
k--;
}
// CASE IV
// Now k is even
// Now we deal with pairs
// Each time a pair is multiplied to
// product i.e.. two elements are added to
// subsequence each time Effectively k becomes half
// Hence, k >>= 1 means k /= 2
k >>= 1;
// Now finding k corresponding pairs
// to get maximum possible value of product
for (int itr = 0; itr < k; itr++) {
// product from left pointers
int left_product = A[i] * A[i + 1];
// product from right pointers
int right_product = A[j] * A[j - 1];
// Taking the max product from two choices
// Correspondingly changing the pointer's position
if (left_product > right_product) {
product *= left_product;
i += 2;
}
else {
product *= right_product;
j -= 2;
}
}
// Finally return product
return product;
}
// driver program
public static void Main()
{
int[] A = { 1, 2, -1, -3, -6, 4 };
int n = A.Length;
int k = 4;
Console.WriteLine(maxProductSubarrayOfSizeK(A, n, k));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP code to find maximum possible product of
// sub-sequence of size k from given array of n
// integers
// Required function
function maxProductSubarrayOfSizeK($A, $n, $k)
{
// sorting given input array
sort($A);
// variable to store final product of all element
// of sub-sequence of size k
$product = 1;
// CASE I
// If max element is 0 and
// k is odd then max product will be 0
if ($A[$n - 1] == 0 && ($k & 1))
return 0;
// CASE II
// If all elements are negative and
// k is odd then max product will be
// product of rightmost-subarray of size k
if ($A[$n - 1] <= 0 && ($k & 1))
{
for ($i = $n - 1; $i >= $n - $k; $i--)
$product *= $A[$i];
return $product;
}
// else
// i is current left pointer index
$i = 0;
// j is current right pointer index
$j = $n - 1;
// CASE III
// if k is odd and rightmost element in
// sorted array is positive then it
// must come in subsequence
// Multiplying A[j] with product and
// correspondingly changing j
if ($k & 1)
{
$product *= $A[$j];
$j--;
$k--;
}
// CASE IV
// Now k is even
// Now we deal with pairs
// Each time a pair is multiplied to product
// ie.. two elements are added to subsequence each time
// Effectively k becomes half
// Hence, k >>= 1 means k /= 2
$k >>= 1;
// Now finding k corresponding pairs
// to get maximum possible value of product
for ($itr = 0; $itr < $k; $itr++)
{
// product from left pointers
$left_product = $A[$i] * $A[$i + 1];
// product from right pointers
$right_product = $A[$j] * $A[$j - 1];
// Taking the max product from two choices
// Correspondingly changing the pointer's position
if ($left_product > $right_product)
{
$product *= $left_product;
$i += 2;
}
else
{
$product *= $right_product;
$j -= 2;
}
}
// Finally return product
return $product;
}
// Driver Code
$A = array(1, 2, -1, -3, -6, 4 );
$n = count($A);
$k = 4;
echo maxProductSubarrayOfSizeK($A, $n, $k);
// This code is contributed by ajit.
?>
Javascript
<script>
// Javascript program to find maximum possible
// product of sub-sequence of size k
// from given array of n integers
// Function to find maximum possible product
function maxProductSubarrayOfSizeK(A, n, k)
{
// sorting given input array
A.sort(function(a, b){return a - b});
// variable to store final product of
// all element of sub-sequence of size k
let product = 1;
let i;
// CASE I
// If max element is 0 and
// k is odd then max product will be 0
if (A[n - 1] == 0 && k % 2 != 0)
return 0;
// CASE II
// If all elements are negative and
// k is odd then max product will be
// product of rightmost-subarray of size k
if (A[n - 1] <= 0 && k % 2 != 0) {
for (i = n - 1; i >= n - k; i--)
product *= A[i];
return product;
}
// else
// i is current left pointer index
i = 0;
// j is current right pointer index
let j = n - 1;
// CASE III
// if k is odd and rightmost element in
// sorted array is positive then it
// must come in subsequence
// Multiplying A[j] with product and
// correspondingly changing j
if (k % 2 != 0) {
product *= A[j];
j--;
k--;
}
// CASE IV
// Now k is even
// Now we deal with pairs
// Each time a pair is multiplied to
// product i.e.. two elements are added to
// subsequence each time Effectively k becomes half
// Hence, k >>= 1 means k /= 2
k >>= 1;
// Now finding k corresponding pairs
// to get maximum possible value of product
for (let itr = 0; itr < k; itr++) {
// product from left pointers
let left_product = A[i] * A[i + 1];
// product from right pointers
let right_product = A[j] * A[j - 1];
// Taking the max product from two choices
// Correspondingly changing the pointer's position
if (left_product > right_product) {
product *= left_product;
i += 2;
}
else {
product *= right_product;
j -= 2;
}
}
// Finally return product
return product;
}
let A = [ 1, 2, -1, -3, -6, 4 ];
let n = A.length;
let k = 4;
document.write(maxProductSubarrayOfSizeK(A, n, k));
</script>
Producción
144
Complejidad de tiempo: O (n * log n), O (n * log n) de la clasificación + O (k) de un recorrido en la array = O (n * log n)
Espacio auxiliar: O (1)
Este artículo es una contribución de Pratik Chhajer . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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