Dada una array de enteros, un número y un valor máximo, la tarea es calcular el valor máximo que se puede obtener de los elementos de la array. Cada valor en la array que atraviesa desde el principio se puede sumar o restar del resultado obtenido del índice anterior, de modo que en cualquier punto el resultado no sea menor que 0 ni mayor que el valor máximo dado. Para el índice 0, tome el resultado anterior igual al número dado. En caso de que no haya respuesta posible, imprima -1.
Ejemplos:
Input : arr[] = {2, 1, 7}
Number = 3
Maximum value = 7
Output : 7
The order of addition and subtraction
is: 3(given number) - 2(arr[0]) -
1(arr[1]) + 7(arr[2]).
Input : arr[] = {3, 10, 6, 4, 5}
Number = 1
Maximum value = 15
Output : 9
The order of addition and subtraction
is: 1 + 3 + 10 - 6 - 4 + 5
Prerrequisito: Programación Dinámica | recursividad _
Enfoque ingenuo: use la recursividad para encontrar el valor máximo. En cada posición de índice hay dos opciones, agregar el elemento de array actual al valor obtenido hasta ahora de los elementos anteriores o restar el elemento de array actual del valor obtenido hasta ahora de los elementos anteriores. Comience desde el índice 0, agregue o reste arr[0] del número dado y llame recursivamente al siguiente índice junto con el número actualizado. Cuando se atraviesa toda la array, compare el número actualizado con el valor máximo general del número obtenido hasta el momento.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP code to find maximum
// value of number obtained by
// using array elements recursively.
#include <bits/stdc++.h>
using namespace std;
// Utility function to find maximum possible value
void findMaxValUtil(int arr[], int n, int num,
int maxLimit, int ind, int& ans)
{
// If entire array is traversed, then compare
// current value in num to overall maximum
// obtained so far.
if (ind == n) {
ans = max(ans, num);
return;
}
// Case 1: Subtract current element from value so
// far if result is greater than or equal to zero.
if (num - arr[ind] >= 0)
{
findMaxValUtil(arr, n, num - arr[ind],
maxLimit, ind + 1, ans);
}
// Case 2 : Add current element to value so far
// if result is less than or equal to maxLimit.
if (num + arr[ind] <= maxLimit)
{
findMaxValUtil(arr, n, num + arr[ind],
maxLimit, ind + 1, ans);
}
}
// Function to find maximum possible
// value that can be obtained using
// array elements and given number.
int findMaxVal(int arr[], int n,
int num, int maxLimit)
{
// variable to store maximum value
// that can be obtained.
int ans = 0;
// variable to store current index position.
int ind = 0;
// call to utility function to find maximum
// possible value that can be obtained.
findMaxValUtil(arr, n, num, maxLimit, ind, ans);
return ans;
}
// Driver code
int main()
{
int num = 1;
int arr[] = { 3, 10, 6, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int maxLimit = 15;
cout << findMaxVal(arr, n, num, maxLimit);
return 0;
}
Java
// Java code to find maximum
// value of number obtained by
// using array elements recursively.
import java.io.*;
import java.lang.*;
public class GFG {
// variable to store maximum value
// that can be obtained.
static int ans;
// Utility function to find maximum
// possible value
static void findMaxValUtil(int []arr, int n, int num,
int maxLimit, int ind)
{
// If entire array is traversed, then compare
// current value in num to overall maximum
// obtained so far.
if (ind == n) {
ans = Math.max(ans, num);
return;
}
// Case 1: Subtract current element from value so
// far if result is greater than or equal to zero.
if (num - arr[ind] >= 0)
{
findMaxValUtil(arr, n, num - arr[ind],
maxLimit, ind + 1);
}
// Case 2 : Add current element to value so far
// if result is less than or equal to maxLimit.
if (num + arr[ind] <= maxLimit)
{
findMaxValUtil(arr, n, num + arr[ind],
maxLimit, ind + 1);
}
}
// Function to find maximum possible
// value that can be obtained using
// array elements and given number.
static int findMaxVal(int []arr, int n,
int num, int maxLimit)
{
// variable to store current index position.
int ind = 0;
// call to utility function to find maximum
// possible value that can be obtained.
findMaxValUtil(arr, n, num, maxLimit, ind);
return ans;
}
// Driver code
public static void main(String args[])
{
int num = 1;
int []arr = { 3, 10, 6, 4, 5 };
int n = arr.length;
int maxLimit = 15;
System.out.print(findMaxVal(arr, n, num,
maxLimit));
}
}
// This code is contributed by Manish Shaw
// (manishshaw1)
Python3
# Python3 code to find maximum # value of number obtained by # using array elements recursively. # Utility def to find # maximum possible value # variable to store maximum value # that can be obtained. ans = 0; def findMaxValUtil(arr, n, num, maxLimit, ind): global ans # If entire array is traversed, # then compare current value # in num to overall maximum # obtained so far. if (ind == n) : ans = max(ans, num) return # Case 1: Subtract current element # from value so far if result is # greater than or equal to zero. if (num - arr[ind] >= 0) : findMaxValUtil(arr, n, num - arr[ind], maxLimit, ind + 1) # Case 2 : Add current element to # value so far if result is less # than or equal to maxLimit. if (num + arr[ind] <= maxLimit) : findMaxValUtil(arr, n, num + arr[ind], maxLimit, ind + 1) # def to find maximum possible # value that can be obtained using # array elements and given number. def findMaxVal(arr, n, num, maxLimit) : global ans # variable to store # current index position. ind = 0 # call to utility def to # find maximum possible value # that can be obtained. findMaxValUtil(arr, n, num, maxLimit, ind) return ans # Driver code num = 1 arr = [3, 10, 6, 4, 5] n = len(arr) maxLimit = 15 print (findMaxVal(arr, n, num, maxLimit)) # This code is contributed by Manish Shaw # (manishshaw1)
C#
// C# code to find maximum
// value of number obtained by
// using array elements recursively.
using System;
using System.Collections.Generic;
class GFG {
// Utility function to find maximum
// possible value
static void findMaxValUtil(int []arr, int n, int num,
int maxLimit, int ind, ref int ans)
{
// If entire array is traversed, then compare
// current value in num to overall maximum
// obtained so far.
if (ind == n) {
ans = Math.Max(ans, num);
return;
}
// Case 1: Subtract current element from value so
// far if result is greater than or equal to zero.
if (num - arr[ind] >= 0)
{
findMaxValUtil(arr, n, num - arr[ind],
maxLimit, ind + 1, ref ans);
}
// Case 2 : Add current element to value so far
// if result is less than or equal to maxLimit.
if (num + arr[ind] <= maxLimit)
{
findMaxValUtil(arr, n, num + arr[ind],
maxLimit, ind + 1, ref ans);
}
}
// Function to find maximum possible
// value that can be obtained using
// array elements and given number.
static int findMaxVal(int []arr, int n,
int num, int maxLimit)
{
// variable to store maximum value
// that can be obtained.
int ans = 0;
// variable to store current index position.
int ind = 0;
// call to utility function to find maximum
// possible value that can be obtained.
findMaxValUtil(arr, n, num, maxLimit, ind,
ref ans);
return ans;
}
// Driver code
public static void Main()
{
int num = 1;
int []arr = { 3, 10, 6, 4, 5 };
int n = arr.Length;
int maxLimit = 15;
Console.Write(findMaxVal(arr, n, num,
maxLimit));
}
}
// This code is contributed by Manish Shaw
// (manishshaw1)
PHP
<?php
// PHP code to find maximum
// value of number obtained by
// using array elements recursively.
// Utility function to find
// maximum possible value
function findMaxValUtil($arr, $n,
$num, $maxLimit,
$ind, &$ans)
{
// If entire array is traversed,
// then compare current value
// in num to overall maximum
// obtained so far.
if ($ind == $n)
{
$ans = max($ans, $num);
return;
}
// Case 1: Subtract current element
// from value so far if result is
// greater than or equal to zero.
if ($num - $arr[$ind] >= 0)
{
findMaxValUtil($arr, $n,
$num - $arr[$ind],
$maxLimit, $ind + 1,
$ans);
}
// Case 2 : Add current element to
// value so far if result is less
// than or equal to maxLimit.
if ($num + $arr[$ind] <= $maxLimit)
{
findMaxValUtil($arr, $n,
$num + $arr[$ind],
$maxLimit, $ind + 1,
$ans);
}
}
// Function to find maximum possible
// value that can be obtained using
// array elements and given number.
function findMaxVal($arr, $n,
$num, $maxLimit)
{
// variable to store maximum value
// that can be obtained.
$ans = 0;
// variable to store
// current index position.
$ind = 0;
// call to utility function to
// find maximum possible value
// that can be obtained.
findMaxValUtil($arr, $n, $num,
$maxLimit, $ind, $ans);
return $ans;
}
// Driver code
$num = 1;
$arr = array(3, 10, 6, 4, 5);
$n = count($arr);
$maxLimit = 15;
echo (findMaxVal($arr, $n, $num, $maxLimit));
//This code is contributed by Manish Shaw
//(manishshaw1)
?>
Javascript
<script>
// Javascript code to find maximum
// value of number obtained by
// using array elements recursively.
// variable to store maximum value
// that can be obtained.
let ans = 0;
// Utility function to find maximum
// possible value
function findMaxValUtil(arr, n, num, maxLimit, ind)
{
// If entire array is traversed, then
// compare current value in num to
// overall maximum obtained so far.
if (ind == n)
{
ans = Math.max(ans, num);
return;
}
// Case 1: Subtract current element
// from value so far if result is
// greater than or equal to zero.
if (num - arr[ind] >= 0)
{
findMaxValUtil(arr, n, num - arr[ind],
maxLimit, ind + 1);
}
// Case 2 : Add current element to value so far
// if result is less than or equal to maxLimit.
if (num + arr[ind] <= maxLimit)
{
findMaxValUtil(arr, n, num + arr[ind],
maxLimit, ind + 1);
}
}
// Function to find maximum possible
// value that can be obtained using
// array elements and given number.
function findMaxVal(arr, n, num, maxLimit)
{
// Variable to store current index position.
let ind = 0;
// Call to utility function to find maximum
// possible value that can be obtained.
findMaxValUtil(arr, n, num, maxLimit, ind);
return ans;
}
// Driver code
let num = 1;
let arr = [ 3, 10, 6, 4, 5 ];
let n = arr.length;
let maxLimit = 15;
document.write(findMaxVal(arr, n, num,
maxLimit));
// This code is contributed by mukesh07
</script>
Producción:
9
Complejidad del tiempo: O(2^n).
Nota: para valores pequeños de n <= 20, esta solución funcionará. Pero a medida que aumenta el tamaño de la array, esta no será una solución óptima.
Una solución eficiente es utilizar la Programación Dinámica . Observe que el valor en cada paso está restringido entre 0 y maxLimit y, por lo tanto, el valor máximo requerido también se encontrará en este rango. En cada posición de índice, después de que arr[i] se suma o se resta del resultado, el nuevo valor de resultado también se encontrará en este rango. Intentemos construir la solución al revés. Suponga que el valor máximo posible requerido es x, donde 0 ≤ x ≤ maxLimit. Este valor x se obtiene sumando o restando arr[n-1] al valor obtenido hasta la posición de índice n-2. Se puede dar la misma razón para el valor obtenido en la posición de índice n-2 que depende del valor en la posición de índice n-3 y así sucesivamente. La relación de recurrencia resultante se puede dar como:
Check can x be obtained from arr[0..n-1]: Check can x - arr[n-1] be obtained from arr[0..n-2] || Check can x + arr[n-1] be obtained from arr[0..n-2]
Se puede crear una tabla booleana de DP en la que dp[i][j] es 1 si el valor j se puede obtener usando arr[0..i] y 0 si no. Para cada posición de índice, comience desde j = 0 y muévase al valor maxLimit, y establezca dp[i][j] en 0 o 1 como se describe anteriormente. Encuentre el valor máximo posible que se puede obtener en la posición de índice n-1 al encontrar el j máximo cuando i = n-1 y dp[n-1][j] = 1.
C++
// C++ program to find maximum value of
// number obtained by using array
// elements by using dynamic programming.
#include <bits/stdc++.h>
using namespace std;
// Function to find maximum possible
// value of number that can be
// obtained using array elements.
int findMaxVal(int arr[], int n,
int num, int maxLimit)
{
// Variable to represent current index.
int ind;
// Variable to show value between
// 0 and maxLimit.
int val;
// Table to store whether a value can
// be obtained or not upto a certain index.
// 1. dp[i][j] = 1 if value j can be
// obtained upto index i.
// 2. dp[i][j] = 0 if value j cannot be
// obtained upto index i.
int dp[n][maxLimit+1];
for(ind = 0; ind < n; ind++)
{
for(val = 0; val <= maxLimit; val++)
{
// Check for index 0 if given value
// val can be obtained by either adding
// to or subtracting arr[0] from num.
if(ind == 0)
{
if(num - arr[ind] == val ||
num + arr[ind] == val)
{
dp[ind][val] = 1;
}
else
{
dp[ind][val] = 0;
}
}
else
{
// 1. If arr[ind] is added to
// obtain given val then val-
// arr[ind] should be obtainable
// from index ind-1.
// 2. If arr[ind] is subtracted to
// obtain given val then val+arr[ind]
// should be obtainable from index ind-1.
// Check for both the conditions.
if(val - arr[ind] >= 0 &&
val + arr[ind] <= maxLimit)
{
// If either of one condition is true,
// then val is obtainable at index ind.
dp[ind][val] = dp[ind-1][val-arr[ind]] ||
dp[ind-1][val+arr[ind]];
}
else if(val - arr[ind] >= 0)
{
dp[ind][val] = dp[ind-1][val-arr[ind]];
}
else if(val + arr[ind] <= maxLimit)
{
dp[ind][val] = dp[ind-1][val+arr[ind]];
}
else
{
dp[ind][val] = 0;
}
}
}
}
// Find maximum value that is obtained
// at index n-1.
for(val = maxLimit; val >= 0; val--)
{
if(dp[n-1][val])
{
return val;
}
}
// If no solution exists return -1.
return -1;
}
// Driver Code
int main()
{
int num = 1;
int arr[] = {3, 10, 6, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int maxLimit = 15;
cout << findMaxVal(arr, n, num, maxLimit);
return 0;
}
Java
// Java program to find maximum
// value of number obtained by
// using array elements by using
// dynamic programming.
import java.io.*;
class GFG
{
// Function to find maximum
// possible value of number
// that can be obtained
// using array elements.
static int findMaxVal(int []arr, int n,
int num, int maxLimit)
{
// Variable to represent
// current index.
int ind;
// Variable to show value
// between 0 and maxLimit.
int val;
// Table to store whether
// a value can be obtained
// or not upto a certain
// index 1. dp[i,j] = 1 if
// value j can be obtained
// upto index i.
// 2. dp[i,j] = 0 if value j
// cannot be obtained upto index i.
int [][]dp = new int[n][maxLimit + 1];
for(ind = 0; ind < n; ind++)
{
for(val = 0; val <= maxLimit; val++)
{
// Check for index 0 if given
// value val can be obtained
// by either adding to or
// subtracting arr[0] from num.
if(ind == 0)
{
if(num - arr[ind] == val ||
num + arr[ind] == val)
{
dp[ind][val] = 1;
}
else
{
dp[ind][val] = 0;
}
}
else
{
// 1. If arr[ind] is added
// to obtain given val then
// val- arr[ind] should be
// obtainable from index
// ind-1.
// 2. If arr[ind] is subtracted
// to obtain given val then
// val+arr[ind] should be
// obtainable from index ind-1.
// Check for both the conditions.
if(val - arr[ind] >= 0 &&
val + arr[ind] <= maxLimit)
{
// If either of one condition
// is true, then val is
// obtainable at index ind.
if(dp[ind - 1][val - arr[ind]] == 1
|| dp[ind - 1][val + arr[ind]] == 1)
dp[ind][val] = 1;
}
else if(val - arr[ind] >= 0)
{
dp[ind][val] = dp[ind - 1][val -
arr[ind]];
}
else if(val + arr[ind] <= maxLimit)
{
dp[ind][val] = dp[ind - 1][val +
arr[ind]];
}
else
{
dp[ind][val] = 0;
}
}
}
}
// Find maximum value that
// is obtained at index n-1.
for(val = maxLimit; val >= 0; val--)
{
if(dp[n - 1][val] == 1)
{
return val;
}
}
// If no solution
// exists return -1.
return -1;
}
// Driver Code
public static void main(String args[])
{
int num = 1;
int []arr = new int[]{3, 10, 6, 4, 5};
int n = arr.length;
int maxLimit = 15;
System.out.print(findMaxVal(arr, n,
num, maxLimit));
}
}
// This code is contributed
// by Manish Shaw(manishshaw1)
Python3
# Python3 program to find maximum # value of number obtained by # using array elements by using # dynamic programming. # Function to find maximum # possible value of number # that can be obtained # using array elements. def findMaxVal(arr, n, num, maxLimit): # Variable to represent # current index. ind = -1; # Variable to show value # between 0 and maxLimit. val = -1; # Table to store whether # a value can be obtained # or not upto a certain # index 1. dp[i,j] = 1 if # value j can be obtained # upto index i. # 2. dp[i,j] = 0 if value j # cannot be obtained upto index i. dp = [[0 for i in range(maxLimit + 1)] for j in range(n)]; for ind in range(n): for val in range(maxLimit + 1): # Check for index 0 if given # value val can be obtained # by either adding to or # subtracting arr[0] from num. if (ind == 0): if (num - arr[ind] == val or num + arr[ind] == val): dp[ind][val] = 1; else: dp[ind][val] = 0; else: # 1. If arr[ind] is added # to obtain given val then # val- arr[ind] should be # obtainable from index # ind-1. # 2. If arr[ind] is subtracted # to obtain given val then # val+arr[ind] should be # obtainable from index ind-1. # Check for both the conditions. if (val - arr[ind] >= 0 and val + arr[ind] <= maxLimit): # If either of one condition # is True, then val is # obtainable at index ind. if (dp[ind - 1][val - arr[ind]] == 1 or dp[ind - 1][val + arr[ind]] == 1): dp[ind][val] = 1; elif (val - arr[ind] >= 0): dp[ind][val] = dp[ind - 1][val - arr[ind]]; elif (val + arr[ind] <= maxLimit): dp[ind][val] = dp[ind - 1][val + arr[ind]]; else: dp[ind][val] = 0; # Find maximum value that # is obtained at index n-1. for val in range(maxLimit, -1, -1): if (dp[n - 1][val] == 1): return val; # If no solution # exists return -1. return -1; # Driver Code if __name__ == '__main__': num = 1; arr = [3, 10, 6, 4, 5]; n = len(arr); maxLimit = 15; print(findMaxVal(arr, n, num, maxLimit)); # This code is contributed by 29AjayKumar
C#
// C# program to find maximum value of
// number obtained by using array
// elements by using dynamic programming.
using System;
class GFG {
// Function to find maximum possible
// value of number that can be
// obtained using array elements.
static int findMaxVal(int []arr, int n,
int num, int maxLimit)
{
// Variable to represent current index.
int ind;
// Variable to show value between
// 0 and maxLimit.
int val;
// Table to store whether a value can
// be obtained or not upto a certain
// index 1. dp[i,j] = 1 if value j
// can be obtained upto index i.
// 2. dp[i,j] = 0 if value j cannot be
// obtained upto index i.
int [,]dp = new int[n,maxLimit+1];
for(ind = 0; ind < n; ind++)
{
for(val = 0; val <= maxLimit; val++)
{
// Check for index 0 if given
// value val can be obtained
// by either adding to or
// subtracting arr[0] from num.
if(ind == 0)
{
if(num - arr[ind] == val ||
num + arr[ind] == val)
{
dp[ind,val] = 1;
}
else
{
dp[ind,val] = 0;
}
}
else
{
// 1. If arr[ind] is added
// to obtain given val then
// val- arr[ind] should be
// obtainable from index
// ind-1.
// 2. If arr[ind] is subtracted
// to obtain given val then
// val+arr[ind] should be
// obtainable from index ind-1.
// Check for both the conditions.
if(val - arr[ind] >= 0 &&
val + arr[ind] <= maxLimit)
{
// If either of one condition
// is true, then val is
// obtainable at index ind.
if(dp[ind-1,val-arr[ind]] == 1
|| dp[ind-1,val+arr[ind]] == 1)
dp[ind,val] = 1;
}
else if(val - arr[ind] >= 0)
{
dp[ind,val] = dp[ind-1,val-arr[ind]];
}
else if(val + arr[ind] <= maxLimit)
{
dp[ind,val] = dp[ind-1,val+arr[ind]];
}
else
{
dp[ind,val] = 0;
}
}
}
}
// Find maximum value that is obtained
// at index n-1.
for(val = maxLimit; val >= 0; val--)
{
if(dp[n-1,val] == 1)
{
return val;
}
}
// If no solution exists return -1.
return -1;
}
// Driver Code
static void Main()
{
int num = 1;
int []arr = new int[]{3, 10, 6, 4, 5};
int n = arr.Length;
int maxLimit = 15;
Console.Write(
findMaxVal(arr, n, num, maxLimit));
}
}
// This code is contributed by Manish Shaw
// (manishshaw1)
PHP
<?php
// PHP program to find maximum value of
// number obtained by using array
// elements by using dynamic programming.
// Function to find maximum possible
// value of number that can be
// obtained using array elements.
function findMaxVal($arr, $n, $num,
$maxLimit)
{
// Variable to represent
// current index.
$ind;
// Variable to show value between
// 0 and maxLimit.
$val;
// Table to store whether a value can
// be obtained or not upto a certain index.
// 1. dp[i][j] = 1 if value j can be
// obtained upto index i.
// 2. dp[i][j] = 0 if value j cannot be
// obtained upto index i.
$dp[$n][$maxLimit + 1] = array();
for($ind = 0; $ind < $n; $ind++)
{
for($val = 0;
$val <= $maxLimit; $val++)
{
// Check for index 0 if given value
// val can be obtained by either adding
// to or subtracting arr[0] from num.
if($ind == 0)
{
if($num - $arr[$ind] == $val ||
$num + $arr[$ind] == $val)
{
$dp[$ind][$val] = 1;
}
else
{
$dp[$ind][$val] = 0;
}
}
else
{
// 1. If arr[ind] is added to
// obtain given val then val-
// arr[ind] should be obtainable
// from index ind-1.
// 2. If arr[ind] is subtracted to
// obtain given val then val+arr[ind]
// should be obtainable from index ind-1.
// Check for both the conditions.
if($val - $arr[$ind] >= 0 &&
$val + $arr[$ind] <= $maxLimit)
{
// If either of one condition is true,
// then val is obtainable at index ind.
$dp[$ind][$val] = $dp[$ind - 1][$val - $arr[$ind]] ||
$dp[$ind - 1][$val + $arr[$ind]];
}
else if($val - $arr[$ind] >= 0)
{
$dp[$ind][$val] = $dp[$ind - 1][$val - $arr[$ind]];
}
else if($val + $arr[$ind] <= $maxLimit)
{
$dp[$ind][$val] = $dp[$ind - 1][$val + $arr[$ind]];
}
else
{
$dp[$ind][$val] = 0;
}
}
}
}
// Find maximum value that is obtained
// at index n-1.
for($val = $maxLimit; $val >= 0; $val--)
{
if($dp[$n - 1][$val])
{
return $val;
}
}
// If no solution exists return -1.
return -1;
}
// Driver Code
$num = 1;
$arr = array(3, 10, 6, 4, 5);
$n = sizeof($arr);
$maxLimit = 15;
echo findMaxVal($arr, $n, $num, $maxLimit);
// This code is contributed by ajit.
?>
Javascript
<script>
// Javascript program to find maximum value of
// number obtained by using array
// elements by using dynamic programming.
// Function to find maximum possible
// value of number that can be
// obtained using array elements.
function findMaxVal(arr, n, num, maxLimit)
{
// Variable to represent current index.
var ind;
// Variable to show value between
// 0 and maxLimit.
var val;
// Table to store whether a value can
// be obtained or not upto a certain index.
// 1. dp[i][j] = 1 if value j can be
// obtained upto index i.
// 2. dp[i][j] = 0 if value j cannot be
// obtained upto index i.
var dp = Array.from( Array(n), () => Array(maxLimit+1));
for(ind = 0; ind < n; ind++)
{
for(val = 0; val <= maxLimit; val++)
{
// Check for index 0 if given value
// val can be obtained by either adding
// to or subtracting arr[0] from num.
if(ind == 0)
{
if(num - arr[ind] == val ||
num + arr[ind] == val)
{
dp[ind][val] = 1;
}
else
{
dp[ind][val] = 0;
}
}
else
{
// 1. If arr[ind] is added to
// obtain given val then val-
// arr[ind] should be obtainable
// from index ind-1.
// 2. If arr[ind] is subtracted to
// obtain given val then val+arr[ind]
// should be obtainable from index ind-1.
// Check for both the conditions.
if(val - arr[ind] >= 0 &&
val + arr[ind] <= maxLimit)
{
// If either of one condition is true,
// then val is obtainable at index ind.
dp[ind][val] = dp[ind-1][val-arr[ind]] ||
dp[ind-1][val+arr[ind]];
}
else if(val - arr[ind] >= 0)
{
dp[ind][val] = dp[ind-1][val-arr[ind]];
}
else if(val + arr[ind] <= maxLimit)
{
dp[ind][val] = dp[ind-1][val+arr[ind]];
}
else
{
dp[ind][val] = 0;
}
}
}
}
// Find maximum value that is obtained
// at index n-1.
for(val = maxLimit; val >= 0; val--)
{
if(dp[n-1][val])
{
return val;
}
}
// If no solution exists return -1.
return -1;
}
// Driver Code
var num = 1;
var arr = [3, 10, 6, 4, 5];
var n = arr.length;
var maxLimit = 15;
document.write( findMaxVal(arr, n, num, maxLimit));
// This code is contributed by rutvik_56.
</script>
Producción:
9
Complejidad de tiempo: O (n*maxLimit), donde n es el tamaño de la array y maxLimit es el valor máximo dado.
Espacio auxiliar: O (n * maxLimit), n es el tamaño de la array y maxLimit es el valor máximo dado.
Optimización: El espacio requerido se puede reducir a O(2*maxLimit). Tenga en cuenta que en cada posición de índice, solo estamos usando valores de la fila anterior. Entonces, podemos crear una tabla con dos filas, en la que una de las filas almacene el resultado de la iteración anterior y otra para la iteración actual.