Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar el producto máximo de la suma del subarreglo con el elemento máximo de ese subarreglo .
Ejemplos:
Entrada: arr[] = {2, -3, 8, -2, 5}
Salida: 88
Explicación:
El producto máximo requerido se puede obtener usando el subarreglo {8, -2, 5}
Por lo tanto, producto máximo = (8 + ( -2) + 5) * (8) = 88.Entrada: arr[] = {-4, 1, -5, 3, 5}
Salida: 40
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subarreglos de la array dada y para cada subarreglo, calcular la suma del subarreglo y multiplicarlo con el elemento máximo en el subarreglo. Actualice el producto máximo comparándolo con el producto calculado. Después de verificar todos los subarreglos, imprima el producto máximo obtenido después de procesar todo el subarreglo.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar modificando el algoritmo de Kadane para obtener el valor máximo resultante. Siga los pasos a continuación para resolver el problema:
- Realice el Algoritmo de Kadane de acuerdo con los siguientes pasos:
- Inicialice tres variables, digamos, largeSum , currSum , currMax como 0 .
- Recorra la array dada arr[] y realice los siguientes pasos;
- Actualice currSum como currSum + arr[i] y currMax como max(currMax, arr[i]) .
- Actualice el valor de la suma más grande como max(largestSum, currMax * currSum) .
- Si el valor de currSum es menor que 0 , actualice el valor de currMax y currSum como 0 .
- Después de completar los pasos anteriores, devuelva el valor de la suma más grande como el producto máximo resultante de la suma del subarreglo con su elemento máximo.
- Inicialice una variable, por ejemplo, MaximumSum como 0 que almacena el producto máximo de la suma del subarreglo con su elemento máximo.
- Realice el algoritmo de Kadane actualizado con la array dada y almacene el valor devuelto en maximumSum .
- Ahora, actualice cada elemento de la array multiplicando cada elemento por (-1) y vuelva a realizar el Algoritmo de Kadane actualizado con la array actualizada, de modo que si el elemento máximo de cualquier subarreglo es negativo, entonces se debe tener en cuenta esa combinación.
- Actualice el valor de maximumSum al máximo de maximumSum y el valor devuelto por el paso anterior.
- Después de completar los pasos anteriores, imprima el valor de maximumSum como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum product
// of the sum of the subarray with its
// maximum element
int Kadane(int arr[], int n)
{
int largestSum = 0, currMax = 0;
int currSum = 0;
// Traverse the array arr[]
for (int i = 0; i < n; i++) {
// Increment currSum by a[i]
currSum += arr[i];
// Maximize the value of currMax
currMax = max(currMax, arr[i]);
// Maximize the value of
// largestSum
largestSum = max(largestSum,
currMax * currSum);
// If currSum goes less than 0
// then update currSum = 0
if (currSum < 0) {
currMax = 0;
currSum = 0;
}
}
// Return the resultant value
return largestSum;
}
// Function to maximize the product of
// the sum of the subarray with its
// maximum element
int maximumWeight(int arr[], int n)
{
// Find the largest sum of the
// subarray
int largestSum = Kadane(arr, n);
// Multiply each array element
// with -1
for (int i = 0; i < n; i++) {
arr[i] = -arr[i];
}
// Find the largest sum of the
// subarray with negation of all
// array element
largestSum = max(largestSum,
Kadane(arr, n));
// Return the resultant maximum
// value
return largestSum;
}
// Driver Code
int main()
{
int arr[] = { 2, -3, 8, -2, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << maximumWeight(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to find the maximum product
// of the sum of the subarray with its
// maximum element
static int Kadane(int arr[], int n)
{
int largestSum = 0, currMax = 0;
int currSum = 0;
// Traverse the array arr[]
for (int i = 0; i < n; i++) {
// Increment currSum by a[i]
currSum += arr[i];
// Maximize the value of currMax
currMax = Math.max(currMax, arr[i]);
// Maximize the value of
// largestSum
largestSum
= Math.max(largestSum, currMax * currSum);
// If currSum goes less than 0
// then update currSum = 0
if (currSum < 0) {
currMax = 0;
currSum = 0;
}
}
// Return the resultant value
return largestSum;
}
// Function to maximize the product of
// the sum of the subarray with its
// maximum element
static int maximumWeight(int arr[], int n)
{
// Find the largest sum of the
// subarray
int largestSum = Kadane(arr, n);
// Multiply each array element
// with -1
for (int i = 0; i < n; i++) {
arr[i] = -arr[i];
}
// Find the largest sum of the
// subarray with negation of all
// array element
largestSum = Math.max(largestSum, Kadane(arr, n));
// Return the resultant maximum
// value
return largestSum;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, -3, 8, -2, 5 };
int N = arr.length;
System.out.println(maximumWeight(arr, N));
// This code is contributed by Potta Lokesh
}
}
Python3
# Python3 program for the above approach # Function to find the maximum product # of the sum of the subarray with its # maximum element def Kadane(arr, n): largestSum = 0 currMax = 0 currSum = 0 # Traverse the array arr[] for i in range(n): # Increment currSum by a[i] currSum += arr[i] # Maximize the value of currMax currMax = max(currMax, arr[i]) # Maximize the value of # largestSum largestSum = max(largestSum, currMax * currSum) # If currSum goes less than 0 # then update currSum = 0 if (currSum < 0): currMax = 0 currSum = 0 # Return the resultant value return largestSum # Function to maximize the product of # the sum of the subarray with its # maximum element def maximumWeight(arr, n): # Find the largest sum of the # subarray largestSum = Kadane(arr, n) # Multiply each array element # with -1 for i in range(n): arr[i] = -arr[i] # Find the largest sum of the # subarray with negation of all # array element largestSum = max(largestSum, Kadane(arr, n)) # Return the resultant maximum # value return largestSum # Driver Code if __name__ == '__main__': arr = [ 2, -3, 8, -2, 5 ] N = len(arr) print(maximumWeight(arr, N)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the maximum product
// of the sum of the subarray with its
// maximum element
static int Kadane(int []arr, int n)
{
int largestSum = 0, currMax = 0;
int currSum = 0;
// Traverse the array arr[]
for(int i = 0; i < n; i++)
{
// Increment currSum by a[i]
currSum += arr[i];
// Maximize the value of currMax
currMax = Math.Max(currMax, arr[i]);
// Maximize the value of
// largestSum
largestSum = Math.Max(largestSum,
currMax * currSum);
// If currSum goes less than 0
// then update currSum = 0
if (currSum < 0)
{
currMax = 0;
currSum = 0;
}
}
// Return the resultant value
return largestSum;
}
// Function to maximize the product of
// the sum of the subarray with its
// maximum element
static int maximumWeight(int []arr, int n)
{
// Find the largest sum of the
// subarray
int largestSum = Kadane(arr, n);
// Multiply each array element
// with -1
for(int i = 0; i < n; i++)
{
arr[i] = -arr[i];
}
// Find the largest sum of the
// subarray with negation of all
// array element
largestSum = Math.Max(largestSum,
Kadane(arr, n));
// Return the resultant maximum
// value
return largestSum;
}
// Driver Code
public static void Main()
{
int []arr = { 2, -3, 8, -2, 5 };
int N = arr.Length;
Console.Write(maximumWeight(arr, N));
}
}
// This code is contributed by ipg2016107
Javascript
<script>
// JavaScript Program for the above approach
// Function to find the maximum product
// of the sum of the subarray with its
// maximum element
function Kadane(arr, n) {
let largestSum = 0, currMax = 0;
let currSum = 0;
// Traverse the array arr[]
for (let i = 0; i < n; i++) {
// Increment currSum by a[i]
currSum += arr[i];
// Maximize the value of currMax
currMax = Math.max(currMax, arr[i]);
// Maximize the value of
// largestSum
largestSum = Math.max(largestSum,
currMax * currSum);
// If currSum goes less than 0
// then update currSum = 0
if (currSum < 0) {
currMax = 0;
currSum = 0;
}
}
// Return the resultant value
return largestSum;
}
// Function to maximize the product of
// the sum of the subarray with its
// maximum element
function maximumWeight(arr, n) {
// Find the largest sum of the
// subarray
let largestSum = Kadane(arr, n);
// Multiply each array element
// with -1
for (let i = 0; i < n; i++) {
arr[i] = -arr[i];
}
// Find the largest sum of the
// subarray with negation of all
// array element
largestSum = Math.max(largestSum,
Kadane(arr, n));
// Return the resultant maximum
// value
return largestSum;
}
// Driver Code
let arr = [2, -3, 8, -2, 5];
let N = arr.length;
document.write(maximumWeight(arr, N));
// This code is contributed by Potta Lokesh
</script>
Producción:
88
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por barwarsunil4 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA