Dada una array arr[] de N enteros y un entero X . Podemos elegir cualquier subarreglo y multiplicar todos sus elementos por X . Después de la multiplicación, encuentra el subarreglo con la suma máxima. La tarea es multiplicar el subarreglo de tal manera que se maximice la suma final del subarreglo.
Ejemplos:
Entrada: arr[] = { -3, 8, -2, 1, -6 }, X = -1
Salida: 15
Elija el subarreglo con {-2, 1, -6} y multiplique X.
Ahora el nuevo array es {-3, 8, 2, -1, 6} cuya suma máxima de sub-arrays es 15.
Entrada: arr[] = {1, 2, 4, -10}, X = 2
Salida: 14
Enfoque: El problema no se puede resolver utilizando un enfoque codicioso. El enfoque codicioso falla en muchos casos, siendo uno de ellos a[] = { -3, 8, -2, 1, 6 } y x = -1 . Usaremos Programación Dinámica para resolver el problema anterior. Sea dp[ind][state] , donde ind es el índice actual en la array y hay 3 estados.
- El primer estado define que no se ha elegido ningún subarreglo hasta que el índice ind se multiplique por X .
- El segundo estado define que el elemento actual en el índice ind está en el subarreglo que se multiplica por X .
- El tercer estado define que el subarreglo ya ha sido elegido.
El algoritmo de Kadane se ha utilizado junto con DP para obtener la suma máxima de subarreglo simultáneamente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 5
// Function to return the maximum sum
int func(int idx, int cur, int a[], int dp[N][3], int n, int x)
{
// Base case
if (idx == n)
return 0;
// If already calculated
if (dp[idx][cur] != -1)
return dp[idx][cur];
int ans = 0;
// If no elements have been chosen
if (cur == 0) {
// Do not choose any element and use
// Kadane's algorithm by taking max
ans = max(ans, a[idx] + func(idx + 1, 0, a, dp, n, x));
// Choose the sub-array and multiply x
ans = max(ans, x * a[idx] + func(idx + 1, 1, a, dp, n, x));
}
else if (cur == 1) {
// Choose the sub-array and multiply x
ans = max(ans, x * a[idx] + func(idx + 1, 1, a, dp, n, x));
// End the sub-array multiplication
ans = max(ans, a[idx] + func(idx + 1, 2, a, dp, n, x));
}
else
// No more multiplication
ans = max(ans, a[idx] + func(idx + 1, 2, a, dp, n, x));
// Memoize and return the answer
return dp[idx][cur] = ans;
}
// Function to get the maximum sum
int getMaximumSum(int a[], int n, int x)
{
// Initialize dp with -1
int dp[n][3];
memset(dp, -1, sizeof dp);
// Iterate from every position and find the
// maximum sum which is possible
int maxi = 0;
for (int i = 0; i < n; i++)
maxi = max(maxi, func(i, 0, a, dp, n, x));
return maxi;
}
// Driver code
int main()
{
int a[] = { -3, 8, -2, 1, -6 };
int n = sizeof(a) / sizeof(a[0]);
int x = -1;
cout << getMaximumSum(a, n, x);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int N = 5;
// Function to return the maximum sum
static int func(int idx, int cur, int a[],
int dp[][], int n, int x)
{
// Base case
if (idx == n)
{
return 0;
}
// If already calculated
if (dp[idx][cur] != -1)
{
return dp[idx][cur];
}
int ans = 0;
// If no elements have been chosen
if (cur == 0)
{
// Do not choose any element and use
// Kadane's algorithm by taking max
ans = Math.max(ans, a[idx] +
func(idx + 1, 0, a, dp, n, x));
// Choose the sub-array and multiply x
ans = Math.max(ans, x * a[idx] +
func(idx + 1, 1, a, dp, n, x));
}
else if (cur == 1)
{
// Choose the sub-array and multiply x
ans = Math.max(ans, x * a[idx] +
func(idx + 1, 1, a, dp, n, x));
// End the sub-array multiplication
ans = Math.max(ans, a[idx] +
func(idx + 1, 2, a, dp, n, x));
}
else // No more multiplication
{
ans = Math.max(ans, a[idx] +
func(idx + 1, 2, a, dp, n, x));
}
// Memoize and return the answer
return dp[idx][cur] = ans;
}
// Function to get the maximum sum
static int getMaximumSum(int a[], int n, int x)
{
// Initialize dp with -1
int dp[][] = new int[n][3];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < 3; j++)
{
dp[i][j] = -1;
}
}
// Iterate from every position and find the
// maximum sum which is possible
int maxi = 0;
for (int i = 0; i < n; i++)
{
maxi = Math.max(maxi, func(i, 0, a, dp, n, x));
}
return maxi;
}
// Driver code
public static void main(String[] args)
{
int a[] = {-3, 8, -2, 1, -6};
int n = a.length;
int x = -1;
System.out.println(getMaximumSum(a, n, x));
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 implementation of the approach N = 5 # Function to return the maximum sum def func(idx, cur, a, dp, n, x) : # Base case if (idx == n) : return 0 # If already calculated if (dp[idx][cur] != -1): return dp[idx][cur] ans = 0 # If no elements have been chosen if (cur == 0) : # Do not choose any element and use # Kadane's algorithm by taking max ans = max(ans, a[idx] + func(idx + 1, 0, a, dp, n, x)) # Choose the sub-array and multiply x ans = max(ans, x * a[idx] + func(idx + 1, 1, a, dp, n, x)) elif (cur == 1) : # Choose the sub-array and multiply x ans = max(ans, x * a[idx] + func(idx + 1, 1, a, dp, n, x)) # End the sub-array multiplication ans = max(ans, a[idx] + func(idx + 1, 2, a, dp, n, x)) else : # No more multiplication ans = max(ans, a[idx] + func(idx + 1, 2, a, dp, n, x)) # Memoize and return the answer dp[idx][cur] = ans return dp[idx][cur] # Function to get the maximum sum def getMaximumSum(a, n, x) : # Initialize dp with -1 dp = [[-1 for i in range(3)] for j in range(n)] # Iterate from every position and find the # maximum sum which is possible maxi = 0 for i in range (0, n) : maxi = max(maxi, func(i, 0, a, dp, n, x)) return maxi # Driver code a = [ -3, 8, -2, 1, -6 ] n = len(a) x = -1 print(getMaximumSum(a, n, x)) # This code is contributed by ihritik
C#
// C# implementation of the approach
using System;
class GFG
{
static int N = 5;
// Function to return the maximum sum
static int func(int idx, int cur, int []a,
int [,]dp, int n, int x)
{
// Base case
if (idx == n)
{
return 0;
}
// If already calculated
if (dp[idx,cur] != -1)
{
return dp[idx,cur];
}
int ans = 0;
// If no elements have been chosen
if (cur == 0)
{
// Do not choose any element and use
// Kadane's algorithm by taking max
ans = Math.Max(ans, a[idx] +
func(idx + 1, 0, a, dp, n, x));
// Choose the sub-array and multiply x
ans = Math.Max(ans, x * a[idx] +
func(idx + 1, 1, a, dp, n, x));
}
else if (cur == 1)
{
// Choose the sub-array and multiply x
ans = Math.Max(ans, x * a[idx] +
func(idx + 1, 1, a, dp, n, x));
// End the sub-array multiplication
ans = Math.Max(ans, a[idx] +
func(idx + 1, 2, a, dp, n, x));
}
else // No more multiplication
{
ans = Math.Max(ans, a[idx] +
func(idx + 1, 2, a, dp, n, x));
}
// Memoize and return the answer
return dp[idx,cur] = ans;
}
// Function to get the maximum sum
static int getMaximumSum(int []a, int n, int x)
{
// Initialize dp with -1
int [,]dp = new int[n,3];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < 3; j++)
{
dp[i,j] = -1;
}
}
// Iterate from every position and find the
// maximum sum which is possible
int maxi = 0;
for (int i = 0; i < n; i++)
{
maxi = Math.Max(maxi, func(i, 0, a, dp, n, x));
}
return maxi;
}
// Driver code
public static void Main(String[] args)
{
int []a = {-3, 8, -2, 1, -6};
int n = a.Length;
int x = -1;
Console.WriteLine(getMaximumSum(a, n, x));
}
}
/* This code contributed by PrinciRaj1992 */
PHP
<?php
// PHP implementation of the approach
$N = 5;
// Function to return the maximum sum
function func($idx, $cur, $a, $dp, $n, $x)
{
// Base case
if ($idx == $n)
return 0;
// If already calculated
if ($dp[$idx][$cur] != -1)
return $dp[$idx][$cur];
$ans = 0;
// If no elements have been chosen
if ($cur == 0)
{
// Do not choose any element and use
// Kadane's algorithm by taking max
$ans = max($ans, $a[$idx] +
func($idx + 1, 0, $a, $dp, $n, $x));
// Choose the sub-array and multiply x
$ans = max($ans, $x * $a[$idx] +
func($idx + 1, 1, $a, $dp, $n, $x));
}
else if ($cur == 1)
{
// Choose the sub-array and multiply x
$ans = max($ans, $x * $a[$idx] +
func($idx + 1, 1, $a, $dp, $n, $x));
// End the sub-array multiplication
$ans = max($ans, $a[$idx] +
func($idx + 1, 2, $a, $dp, $n, $x));
}
else
// No more multiplication
$ans = max($ans, $a[$idx] +
func($idx + 1, 2, $a, $dp,$n, $x));
// Memoize and return the answer
return $dp[$idx][$cur] = $ans;
}
// Function to get the maximum sum
function getMaximumSum($a, $n, $x)
{
// Initialize dp with -1
$dp = array(array()) ;
for($i = 0; $i < $n; $i++)
{
for($j = 0; $j < 3; $j++)
{
$dp[$i][$j] = -1;
}
}
// Iterate from every position and find the
// maximum sum which is possible
$maxi = 0;
for ($i = 0; $i < $n; $i++)
$maxi = max($maxi, func($i, 0, $a, $dp, $n, $x));
return $maxi;
}
// Driver code
$a = array( -3, 8, -2, 1, -6 );
$n = count($a) ;
$x = -1;
echo getMaximumSum($a, $n, $x);
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript implementation of the approach
var N = 5;
// Function to return the maximum sum
function func(idx , cur , a , dp , n , x) {
// Base case
if (idx == n) {
return 0;
}
// If already calculated
if (dp[idx][cur] != -1) {
return dp[idx][cur];
}
var ans = 0;
// If no elements have been chosen
if (cur == 0) {
// Do not choose any element and use
// Kadane's algorithm by taking max
ans = Math.max(ans, a[idx] +
func(idx + 1, 0, a, dp, n, x));
// Choose the sub-array and multiply x
ans = Math.max(ans, x * a[idx] +
func(idx + 1, 1, a, dp, n, x));
} else if (cur == 1) {
// Choose the sub-array and multiply x
ans = Math.max(ans, x * a[idx] +
func(idx + 1, 1, a, dp, n, x));
// End the sub-array multiplication
ans = Math.max(ans, a[idx] +
func(idx + 1, 2, a, dp, n, x));
} else // No more multiplication
{
ans = Math.max(ans, a[idx] +
func(idx + 1, 2, a, dp, n, x));
}
// Memoize and return the answer
return dp[idx][cur] = ans;
}
// Function to get the maximum sum
function getMaximumSum(a , n , x) {
// Initialize dp with -1
var dp = Array(n).fill().map(()=>Array(3).fill(0));
for (i = 0; i < n; i++) {
for (j = 0; j < 3; j++) {
dp[i][j] = -1;
}
}
// Iterate from every position and find the
// maximum sum which is possible
var maxi = 0;
for (i = 0; i < n; i++) {
maxi = Math.max(maxi, func(i, 0, a, dp, n, x));
}
return maxi;
}
// Driver code
var a = [ -3, 8, -2, 1, -6 ];
var n = a.length;
var x = -1;
document.write(getMaximumSum(a, n, x));
// This code contributed by Rajput-Ji
</script>
Producción:
15
Complejidad de Tiempo: O(N * 3)
Espacio Auxiliar: O(N * 3)