Dada una secuencia de array [A 1 , A 2 …A n ], la tarea es encontrar la máxima suma posible de la subsecuencia creciente S de longitud k tal que S 1 <=S 2 <=S 3 ………<=S k .
Ejemplos:
Entrada:
n = 8 k = 3
A=[8 5 9 10 5 6 21 8]
Salida: 40
Posible subsecuencia creciente de Longitud 3 con la suma máxima posible es 9 10 21Entrada:
n = 9 k = 4
A=[2 5 3 9 15 33 6 18 20]
Salida: 62
Posible subsecuencia creciente de Longitud 4 con la suma máxima posible es 9 15 18 20
Una cosa que es claramente visible que se puede resolver fácilmente con programación dinámica y este problema es una variación simple de la subsecuencia creciente más larga . Si no sabe cómo calcular la subsecuencia creciente más larga, consulte la implementación en el enlace.
Enfoque ingenuo:
en el enfoque de fuerza bruta, primero intentaremos encontrar todas las subsecuencias de longitud k y verificaremos si son crecientes o no. Podría haber n C k tales secuencias en el peor de los casos cuando todos los elementos están en orden creciente. Ahora encontraremos la suma máxima posible para tales secuencias.
La complejidad del tiempo sería O(( n C k )*n).
Enfoque eficiente:
usaremos una array dp bidimensional en la que dp[i][l] significa que la subsecuencia de suma máxima de longitud l toma valores de array de 0 a i y la subsecuencia termina en el índice ‘i’. El rango de ‘l’ es de 0 a k-1. Usando el enfoque de una subsecuencia creciente más larga en el ciclo interno cuando j<i, verificaremos si arr[j] < arr[i] para verificar si la subsecuencia aumenta.
Este problema se puede dividir en sus subproblemas:
dp[i][1]=arr[i] para la longitud 1, la subsecuencia creciente máxima es igual al valor de la array
dp[i][l+1]= max(dp[i][l+1], dp[j ][l]+arr[i]) para cualquier longitud l entre 1 y k-1
Esto significa que si para la i-ésima posición y subsecuencia de longitud l+1, existe alguna subsecuencia en j (j < i) de longitud l para la cual la suma de dp[j][l] + arr[i] es mayor que su inicial valor calculado y luego actualice ese valor.
Luego, finalmente encontraremos el valor máximo de dp[i][k], es decir, para cada ‘i’ si la subsecuencia de k longitud está causando más suma que actualizar la respuesta requerida.
A continuación se muestra el código de implementación:
C++
/*C++ program to calculate the maximum sum of
increasing subsequence of length k*/
#include <bits/stdc++.h>
using namespace std;
int MaxIncreasingSub(int arr[], int n, int k)
{
// In the implementation dp[n][k] represents
// maximum sum subsequence of length k and the
// subsequence is ending at index n.
int dp[n][k + 1], ans = -1;
// Initializing whole multidimensional
// dp array with value -1
memset(dp, -1, sizeof(dp));
// For each ith position increasing subsequence
// of length 1 is equal to that array ith value
// so initializing dp[i][1] with that array value
for (int i = 0; i < n; i++) {
dp[i][1] = arr[i];
}
// Starting from 1st index as we have calculated
// for 0th index. Computing optimized dp values
// in bottom-up manner
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
// check for increasing subsequence
if (arr[j] < arr[i]) {
for (int l = 1; l <= k - 1; l++) {
// Proceed if value is pre calculated
if (dp[j][l] != -1) {
// Check for all the subsequences
// ending at any j<i and try including
// element at index i in them for
// some length l. Update the maximum
// value for every length.
dp[i][l + 1] = max(dp[i][l + 1],
dp[j][l] + arr[i]);
}
}
}
}
}
// The final result would be the maximum
// value of dp[i][k] for all different i.
for (int i = 0; i < n; i++) {
if (ans < dp[i][k])
ans = dp[i][k];
}
// When no subsequence of length k is
// possible sum would be considered zero
return (ans == -1) ? 0 : ans;
}
// Driver function
int main()
{
int n = 8, k = 3;
int arr[n] = { 8, 5, 9, 10, 5, 6, 21, 8 };
int ans = MaxIncreasingSub(arr, n, k);
cout << ans << "\n";
return 0;
}
Java
/*Java program to calculate the maximum sum of
increasing subsequence of length k*/
import java.util.*;
class GFG
{
static int MaxIncreasingSub(int arr[], int n, int k)
{
// In the implementation dp[n][k] represents
// maximum sum subsequence of length k and the
// subsequence is ending at index n.
int dp[][]=new int[n][k + 1], ans = -1;
// Initializing whole multidimensional
// dp array with value -1
for(int i = 0; i < n; i++)
for(int j = 0; j < k + 1; j++)
dp[i][j]=-1;
// For each ith position increasing subsequence
// of length 1 is equal to that array ith value
// so initializing dp[i][1] with that array value
for (int i = 0; i < n; i++)
{
dp[i][1] = arr[i];
}
// Starting from 1st index as we have calculated
// for 0th index. Computing optimized dp values
// in bottom-up manner
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
// check for increasing subsequence
if (arr[j] < arr[i])
{
for (int l = 1; l <= k - 1; l++)
{
// Proceed if value is pre calculated
if (dp[j][l] != -1)
{
// Check for all the subsequences
// ending at any j<i and try including
// element at index i in them for
// some length l. Update the maximum
// value for every length.
dp[i][l + 1] = Math.max(dp[i][l + 1],
dp[j][l] + arr[i]);
}
}
}
}
}
// The final result would be the maximum
// value of dp[i][k] for all different i.
for (int i = 0; i < n; i++)
{
if (ans < dp[i][k])
ans = dp[i][k];
}
// When no subsequence of length k is
// possible sum would be considered zero
return (ans == -1) ? 0 : ans;
}
// Driver code
public static void main(String args[])
{
int n = 8, k = 3;
int arr[] = { 8, 5, 9, 10, 5, 6, 21, 8 };
int ans = MaxIncreasingSub(arr, n, k);
System.out.println(ans );
}
}
// This code is contributed by Arnab Kundu
Python3
# Python program to calculate the maximum sum # of increasing subsequence of length k def MaxIncreasingSub(arr, n, k): # In the implementation dp[n][k] represents # maximum sum subsequence of length k and the # subsequence is ending at index n. dp = [-1]*n ans = -1 # Initializing whole multidimensional # dp array with value - 1 for i in range(n): dp[i] = [-1]*(k+1) # For each ith position increasing subsequence # of length 1 is equal to that array ith value # so initializing dp[i][1] with that array value for i in range(n): dp[i][1] = arr[i] # Starting from 1st index as we have calculated # for 0th index. Computing optimized dp values # in bottom-up manner for i in range(1,n): for j in range(i): # check for increasing subsequence if arr[j] < arr[i]: for l in range(1,k): # Proceed if value is pre calculated if dp[j][l] != -1: # Check for all the subsequences # ending at any j < i and try including # element at index i in them for # some length l. Update the maximum # value for every length. dp[i][l+1] = max(dp[i][l+1], dp[j][l] + arr[i]) # The final result would be the maximum # value of dp[i][k] for all different i. for i in range(n): if ans < dp[i][k]: ans = dp[i][k] # When no subsequence of length k is # possible sum would be considered zero return (0 if ans == -1 else ans) # Driver Code if __name__ == "__main__": n, k = 8, 3 arr = [8, 5, 9, 10, 5, 6, 21, 8] ans = MaxIncreasingSub(arr, n, k) print(ans) # This code is contributed by # sanjeev2552
C#
/*C# program to calculate the maximum sum of
increasing subsequence of length k*/
using System;
class GFG
{
static int MaxIncreasingSub(int []arr, int n, int k)
{
// In the implementation dp[n,k] represents
// maximum sum subsequence of length k and the
// subsequence is ending at index n.
int [,]dp=new int[n, k + 1];
int ans = -1;
// Initializing whole multidimensional
// dp array with value -1
for(int i = 0; i < n; i++)
for(int j = 0; j < k + 1; j++)
dp[i, j]=-1;
// For each ith position increasing subsequence
// of length 1 is equal to that array ith value
// so initializing dp[i,1] with that array value
for (int i = 0; i < n; i++)
{
dp[i, 1] = arr[i];
}
// Starting from 1st index as we have calculated
// for 0th index. Computing optimized dp values
// in bottom-up manner
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
// check for increasing subsequence
if (arr[j] < arr[i])
{
for (int l = 1; l <= k - 1; l++)
{
// Proceed if value is pre calculated
if (dp[j, l] != -1)
{
// Check for all the subsequences
// ending at any j<i and try including
// element at index i in them for
// some length l. Update the maximum
// value for every length.
dp[i, l + 1] = Math.Max(dp[i, l + 1],
dp[j, l] + arr[i]);
}
}
}
}
}
// The final result would be the maximum
// value of dp[i,k] for all different i.
for (int i = 0; i < n; i++)
{
if (ans < dp[i, k])
ans = dp[i, k];
}
// When no subsequence of length k is
// possible sum would be considered zero
return (ans == -1) ? 0 : ans;
}
// Driver code
public static void Main(String []args)
{
int n = 8, k = 3;
int []arr = { 8, 5, 9, 10, 5, 6, 21, 8 };
int ans = MaxIncreasingSub(arr, n, k);
Console.WriteLine(ans );
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript program to calculate the
// maximum sum of increasing subsequence
// of length k
function MaxIncreasingSub(arr, n, k)
{
// In the implementation dp[n][k]
// represents maximum sum subsequence
// of length k and the subsequence is
// ending at index n.
let dp = new Array(n);
for(let i = 0; i < dp.length; i++)
{
dp[i] = new Array(2);
}
let ans = -1;
// Initializing whole multidimensional
// dp array with value -1
for(let i = 0; i < n; i++)
for(let j = 0; j < k + 1; j++)
dp[i][j] = -1;
// For each ith position increasing
// subsequence of length 1 is equal
// to that array ith value so
// initializing dp[i][1] with that
// array value
for(let i = 0; i < n; i++)
{
dp[i][1] = arr[i];
}
// Starting from 1st index as we
// have calculated for 0th index.
// Computing optimized dp values
// in bottom-up manner
for(let i = 1; i < n; i++)
{
for(let j = 0; j < i; j++)
{
// Check for increasing subsequence
if (arr[j] < arr[i])
{
for(let l = 1; l <= k - 1; l++)
{
// Proceed if value is pre calculated
if (dp[j][l] != -1)
{
// Check for all the subsequences
// ending at any j<i and try including
// element at index i in them for
// some length l. Update the maximum
// value for every length.
dp[i][l + 1] = Math.max(dp[i][l + 1],
dp[j][l] +
arr[i]);
}
}
}
}
}
// The final result would be the maximum
// value of dp[i][k] for all different i.
for(let i = 0; i < n; i++)
{
if (ans < dp[i][k])
ans = dp[i][k];
}
// When no subsequence of length k is
// possible sum would be considered zero
return(ans == -1) ? 0 : ans;
}
// Driver Code
let n = 8, k = 3;
let arr = [ 8, 5, 9, 10, 5, 6, 21, 8 ];
let ans = MaxIncreasingSub(arr, n, k);
document.write(ans);
// This code is contributed by code_hunt
</script>
40
Complejidad temporal: O(n^2*k)
Complejidad espacial: O(n^2)