Dada una array de n enteros positivos, escriba un programa para encontrar la suma máxima de subsecuencias crecientes desde el prefijo hasta el i-ésimo índice y que también incluya un k-ésimo elemento dado que está después de i, es decir, k > i.
Ejemplos:
Entrada: arr[] = {1, 101, 2, 3, 100, 4, 5} i-th index = 4 (El elemento en el 4th index es 100) K-th index = 6 (Element en el 6th index es 5.)
Salida: 11
Explicación:
Entonces necesitamos calcular la suma máxima de la subsecuencia (1 101 2 3 100 5) tal que 5 esté necesariamente incluido en la subsecuencia, entonces la respuesta es 11 por la subsecuencia (1 2 3 5).Entrada: arr[] = {1, 101, 2, 3, 100, 4, 5} i-th index = 2 (El elemento en el 2nd index es 2) K-th index = 5 (Element en el 5th index es 4.)
Salida: 7
Explicación:
Entonces necesitamos calcular la suma máxima de la subsecuencia (1 101 2 4) tal que 4 esté necesariamente incluido en la subsecuencia, entonces la respuesta es 7 por la subsecuencia (1 2 4).
Requisito previo: Subsecuencia creciente de suma máxima
Enfoque ingenuo:
- Construya una nueva array que contenga elementos hasta el i-ésimo índice y el k-ésimo elemento.
- Calcula recursivamente todas las subsecuencias crecientes.
- Descartar todas las subsecuencias que no tengan el k-ésimo elemento incluido.
- Calcule la suma máxima de las subsecuencias sobrantes y visualícela.
Complejidad del tiempo: O(2 n )
Mejor enfoque: utilice un enfoque dinámico para mantener una tabla dp[][]. El valor de dp[i][k] almacena la suma máxima de la subsecuencia creciente hasta el índice i-ésimo y que contiene el elemento k-ésimo.
C++
// C++ program to find maximum sum increasing
// subsequence till i-th index and including
// k-th index.
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
ll pre_compute(ll a[], ll n, ll index, ll k)
{
ll dp[n][n] = { 0 };
// Initializing the first row of the dp[][].
for (int i = 0; i < n; i++) {
if (a[i] > a[0])
dp[0][i] = a[i] + a[0];
else
dp[0][i] = a[i];
}
// Creating the dp[][] matrix.
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[j] > a[i] && j > i) {
if (dp[i - 1][i] + a[j] > dp[i - 1][j])
dp[i][j] = dp[i - 1][i] + a[j];
else
dp[i][j] = dp[i - 1][j];
}
else
dp[i][j] = dp[i - 1][j];
}
}
// To calculate for i=4 and k=6.
return dp[index][k];
}
int main()
{
ll a[] = { 1, 101, 2, 3, 100, 4, 5 };
ll n = sizeof(a) / sizeof(a[0]);
ll index = 4, k = 6;
printf("%lld", pre_compute(a, n, index, k));
return 0;
}
Java
// Java program to find maximum sum increasing
// subsequence till i-th index and including
// k-th index.
class GFG {
static int pre_compute(int a[], int n,
int index, int k)
{
int dp[][] = new int[n][n];
// Initializing the first row of
// the dp[][].
for (int i = 0; i < n; i++) {
if (a[i] > a[0])
dp[0][i] = a[i] + a[0];
else
dp[0][i] = a[i];
}
// Creating the dp[][] matrix.
for (int i = 1; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (a[j] > a[i] && j > i)
{
if (dp[i - 1][i] + a[j] >
dp[i - 1][j])
dp[i][j] = dp[i - 1][i]
+ a[j];
else
dp[i][j] = dp[i - 1][j];
}
else
dp[i][j] = dp[i - 1][j];
}
}
// To calculate for i=4 and k=6.
return dp[index][k];
}
// Driver code
public static void main(String[] args)
{
int a[] = { 1, 101, 2, 3, 100, 4, 5 };
int n = a.length;
int index = 4, k = 6;
System.out.println(
pre_compute(a, n, index, k));
}
}
// This code is contributed by Smitha.
Python3
# Python3 program to find maximum # sum increasing subsequence till # i-th index and including k-th index. def pre_compute(a, n, index, k): dp = [[0 for i in range(n)] for i in range(n)] # Initializing the first # row of the dp[][] for i in range(n): if a[i] > a[0]: dp[0][i] = a[i] + a[0] else: dp[0][i] = a[i] # Creating the dp[][] matrix. for i in range(1, n): for j in range(n): if a[j] > a[i] and j > i: if dp[i - 1][i] + a[j] > dp[i - 1][j]: dp[i][j] = dp[i - 1][i] + a[j] else: dp[i][j] = dp[i - 1][j] else: dp[i][j] = dp[i - 1][j] # To calculate for i=4 and k=6. return dp[index][k] # Driver code a = [1, 101, 2, 3, 100, 4, 5 ] n = len(a) index = 4 k = 6 print(pre_compute(a, n, index, k)) # This code is contributed # by sahilshelangia
C#
// C# program to find maximum
// sum increasing subsequence
// till i-th index and including
// k-th index.
using System;
class GFG
{
static int pre_compute(int []a, int n,
int index, int k)
{
int [,]dp = new int[n, n];
// Initializing the first
// row of the dp[][].
for (int i = 0; i < n; i++)
{
if (a[i] > a[0])
dp[0, i] = a[i] + a[0];
else
dp[0, i] = a[i];
}
// Creating the dp[][] matrix.
for (int i = 1; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (a[j] > a[i] && j > i)
{
if (dp[i - 1, i] + a[j] >
dp[i - 1, j])
dp[i, j] = dp[i - 1, i] +
a[j];
else
dp[i, j] = dp[i - 1, j];
}
else
dp[i, j] = dp[i - 1, j];
}
}
// To calculate for i=4 and k=6.
return dp[index, k];
}
// Driver code
static public void Main ()
{
int []a = {1, 101, 2,
3, 100, 4, 5};
int n = a.Length;
int index = 4, k = 6;
Console.WriteLine(pre_compute(a, n,
index, k));
}
}
// This code is contributed by @ajit
PHP
<?php
// PHP program to find maximum sum increasing
// subsequence till i-th index and including
// k-th index.
function pre_compute(&$a, $n, $index, $k)
{
$dp = array_fill(0, $n,
array_fill(0, $n, NULL));
// Initializing the first row of the dp[][].
for ($i = 0; $i < $n; $i++)
{
if ($a[$i] > $a[0])
$dp[0][$i] = $a[$i] + $a[0];
else
$dp[0][$i] = $a[$i];
}
// Creating the dp[][] matrix.
for ($i = 1; $i < $n; $i++)
{
for ($j = 0; $j < $n; $j++)
{
if ($a[$j] > $a[$i] && $j > $i)
{
if (($dp[$i - 1][$i] + $a[$j]) >
$dp[$i - 1][$j])
$dp[$i][$j] = $dp[$i - 1][$i] +
$a[$j];
else
$dp[$i][$j] = $dp[$i - 1][$j];
}
else
$dp[$i][$j] = $dp[$i - 1][$j];
}
}
// To calculate for i=4 and k=6.
return $dp[$index][$k];
}
// Driver Code
$a = array( 1, 101, 2, 3, 100, 4, 5 );
$n = sizeof($a);
$index = 4;
$k = 6;
echo pre_compute($a, $n, $index, $k);
// This code is contributed by ita_c
?>
Javascript
<script>
// Javascript program to find maximum
// sum increasing subsequence till
// i-th index and including k-th index.
function pre_compute(a, n, index, k)
{
let dp = new Array(n);
for(let i = 0; i < n; i++)
{
dp[i] = new Array(n);
for(let j = 0; j < n; j++)
{
dp[i][j] = 0;
}
}
// Initializing the first row of
// the dp[][].
for(let i = 0; i < n; i++)
{
if (a[i] > a[0])
dp[0][i] = a[i] + a[0];
else
dp[0][i] = a[i];
}
// Creating the dp[][] matrix.
for(let i = 1; i < n; i++)
{
for(let j = 0; j < n; j++)
{
if (a[j] > a[i] && j > i)
{
if (dp[i - 1][i] + a[j] >
dp[i - 1][j])
dp[i][j] = dp[i - 1][i] +
a[j];
else
dp[i][j] = dp[i - 1][j];
}
else
dp[i][j] = dp[i - 1][j];
}
}
// To calculate for i=4 and k=6.
return dp[index][k];
}
// Driver code
let a = [ 1, 101, 2, 3, 100, 4, 5 ];
let n = a.length;
let index = 4, k = 6;
document.write(pre_compute(a, n, index, k));
// This code is contributed by mukesh07
</script>
Producción
11
Complejidad de Tiempo: O(n 2 )
Espacio Auxiliar: O(n 2 )
Enfoque eficiente: este problema consiste básicamente en encontrar la suma máxima de subsecuencias crecientes hasta el índice dado i que todos los elementos de la subsecuencia son menores que el elemento k-ésimo (índice) o arr[k]. Por lo tanto, encuentre la subsecuencia creciente de suma máxima .
Por ejemplo: arr[] = {1, 101, 2, 3, 100, 4, 5}, índice = 4; k = 6;
Ahora, solo necesitamos encontrar la subsecuencia de suma máxima desde la array hasta el índice 4, dado que todos los elementos de esa subsecuencia son menos que arr[k], que es 5. Ahora, iterando a través de la array.
Para i = 0; como 1 < 5; max subsecuencia creciente {1}, max = 1.
Para i = 1; como 101 > 5; saltar esta entrada. Subsecuencia creciente máxima {1}, máx = 1.
Para i = 2; como 2 < 5; max subsecuencia creciente {1, 2}, max = 3.
Para i = 3; como 3 < 5; max subsecuencia creciente {1, 2, 3}, max = 6.
Para i = 4; como 100 > 5; saltar esta entrada. Subsecuencia creciente máxima {1, 2, 3}, máx = 6.
como índice = 4; por lo tanto, deténgase aquí y la respuesta será max + a[k] = 6 + 5 = 11.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
// Function to find the
// maximum of two numbers
int max(int a, int b)
{
if (a > b) {
return a;
}
return b;
}
// Function to find the sum
int pre_compute(int a[], int n, int index, int k)
{
// Base case
if (index >= k) {
return -1;
}
// Initialize the dp table
int dp[index] = { 0 };
int i;
// Initialize the dp array with
// corresponding array index value
for (i = 0; i <= index; i++) {
dp[i] = a[i];
}
int maxi = INT_MIN;
for (i = 0; i <= index; i++) {
// Only include values
// which are less than a[k]
if (a[i] >= a[k]) {
continue;
}
for (int j = 0; j < i; j++) {
// Check if a[i] is
// greater than a[j]
if (a[i] > a[j]) {
dp[i] = dp[j] + a[i];
}
// Update maxi
maxi = max(maxi, dp[i]);
}
}
// Incase all the elements in
// the array upto ith index
// are greater or equal to a[k]
if (maxi == INT_MIN) {
return a[k];
}
return maxi + a[k];
// Contributed by Mainak Dutta
}
// Driver code
int main()
{
int a[] = { 1, 101, 2, 3, 100, 4, 5 };
int n = sizeof(a) / sizeof(a[0]);
int index = 4, k = 6;
// Function call
printf("%d", pre_compute(a, n, index, k));
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to find the
// maximum of two numbers
static int max(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
// Function to find the sum
static int pre_compute(int a[], int n,
int index, int k)
{
// Base case
if (index >= k)
{
return -1;
}
// Initialize the dp table
int[] dp = new int[index + 1];
int i;
// Initialize the dp array with
// corresponding array index value
for(i = 0; i <= index; i++)
{
dp[i] = a[i];
}
int maxi = Integer.MIN_VALUE;
for(i = 0; i <= index; i++)
{
// Only include values
// which are less than a[k]
if (a[i] >= a[k])
{
continue;
}
for(int j = 0; j < i; j++)
{
// Check if a[i] is
// greater than a[j]
if (a[i] > a[j])
{
dp[i] = dp[j] + a[i];
}
// Update maxi
maxi = max(maxi, dp[i]);
}
}
// Incase all the elements in
// the array upto ith index
// are greater or equal to a[k]
if (maxi == Integer.MIN_VALUE)
{
return a[k];
}
return maxi + a[k];
}
// Driver code
public static void main (String[] args)
{
int a[] = { 1, 101, 2, 3, 100, 4, 5 };
int n = a.length;
int index = 4, k = 6;
System.out.println(pre_compute(a, n, index, k));
}
}
// This code is contributed by rag2127
Python3
# Python3 program for the above approach
# Function to find the sum
def pre_compute(a, n, index, k):
# Base case
if (index >= k):
return -1
# Initialize the dp table
dp = [0 for i in range(index)]
# Initialize the dp array with
# corresponding array index value
for i in range(index):
dp[i] = a[i]
maxi = -float('inf')
for i in range(index):
# Only include values
# which are less than a[k]
if (a[i] >= a[k]):
continue
for j in range(i):
# Check if a[i] is
# greater than a[j]
if (a[i] > a[j]):
dp[i] = dp[j] + a[i]
# Update maxi
maxi = max(maxi, dp[i])
# Incase all the elements in
# the array upto ith index
# are greater or equal to a[k]
if (maxi == -float('inf')):
return a[k]
return maxi + a[k]
# Driver code
a = [ 1, 101, 2, 3, 100, 4, 5 ]
n = len(a)
index = 4
k = 6
# Function call
print(pre_compute(a, n, index, k))
# This code is contributed by rohitsingh07052
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the
// maximum of two numbers
static int max(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
// Function to find the sum
static int pre_compute(int[] a, int n,
int index, int k)
{
// Base case
if (index >= k)
{
return -1;
}
// Initialize the dp table
int[] dp = new int[index + 1];
int i;
// Initialize the dp array with
// corresponding array index value
for(i = 0; i <= index; i++)
{
dp[i] = a[i];
}
int maxi = Int32.MinValue;
for(i = 0; i <= index; i++)
{
// Only include values
// which are less than a[k]
if (a[i] >= a[k])
{
continue;
}
for(int j = 0; j < i; j++)
{
// Check if a[i] is
// greater than a[j]
if (a[i] > a[j])
{
dp[i] = dp[j] + a[i];
}
// Update maxi
maxi = Math.Max(maxi, dp[i]);
}
}
// Incase all the elements in
// the array upto ith index
// are greater or equal to a[k]
if (maxi == Int32.MinValue)
{
return a[k];
}
return maxi + a[k];
}
// Driver code
static public void Main()
{
int[] a = { 1, 101, 2, 3, 100, 4, 5 };
int n = a.Length;
int index = 4, k = 6;
Console.WriteLine(pre_compute(a, n, index, k));
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript program for the above approach
// Function to find the
// maximum of two numbers
function max(a, b)
{
if (a > b)
{
return a;
}
return b;
}
// Function to find the sum
function pre_compute(a, n, index, k)
{
// Base case
if (index >= k)
{
return -1;
}
// Initialize the dp table
let dp = new Array(index + 1);
dp.fill(0);
let i;
// Initialize the dp array with
// corresponding array index value
for(i = 0; i <= index; i++)
{
dp[i] = a[i];
}
let maxi = Number.MIN_VALUE;
for(i = 0; i <= index; i++)
{
// Only include values
// which are less than a[k]
if (a[i] >= a[k])
{
continue;
}
for(let j = 0; j < i; j++)
{
// Check if a[i] is
// greater than a[j]
if (a[i] > a[j])
{
dp[i] = dp[j] + a[i];
}
// Update maxi
maxi = Math.max(maxi, dp[i]);
}
}
// Incase all the elements in
// the array upto ith index
// are greater or equal to a[k]
if (maxi == Number.MIN_VALUE)
{
return a[k];
}
return maxi + a[k];
}
// Driver code
let a = [ 1, 101, 2, 3, 100, 4, 5 ];
let n = a.length;
let index = 4, k = 6;
document.write(pre_compute(a, n, index, k));
// This code is contributed by divyeshrabadiya07
</script>
Producción
11
Complejidad de Tiempo: O( índice 2 )
Espacio Auxiliar: O( índice )
Publicación traducida automáticamente
Artículo escrito por Aditya Gupta 4 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA