Dada una array de n enteros positivos. Escriba un programa para encontrar la suma de la subsecuencia de suma máxima de la array dada de manera que los enteros en la subsecuencia se clasifiquen en orden creciente. Por ejemplo, si la entrada es {1, 101, 2, 3, 100, 4, 5}, la salida debe ser 106 (1 + 2 + 3 + 100), si la array de entrada es {3, 4, 5, 10 }, la salida debe ser 22 (3 + 4 + 5 + 10) y si la array de entrada es {10, 5, 4, 3}, la salida debe ser 10
Solución: Este problema es una variación del problema estándar de subsecuencia creciente más larga (LIS) . Necesitamos un ligero cambio en la solución de programación dinámica del problema LIS . Todo lo que necesitamos cambiar es usar la suma como criterio en lugar de una longitud de subsecuencia creciente.
Las siguientes son las soluciones de Programación Dinámica al problema:
C++
/* Dynamic Programming implementation
of Maximum Sum Increasing Subsequence
(MSIS) problem */
#include <bits/stdc++.h>
using namespace std;
/* maxSumIS() returns the maximum
sum of increasing subsequence
in arr[] of size n */
int maxSumIS(int arr[], int n)
{
int i, j, max = 0;
int msis[n];
/* Initialize msis values
for all indexes */
for ( i = 0; i < n; i++ )
msis[i] = arr[i];
/* Compute maximum sum values
in bottom up manner */
for ( i = 1; i < n; i++ )
for ( j = 0; j < i; j++ )
if (arr[i] > arr[j] &&
msis[i] < msis[j] + arr[i])
msis[i] = msis[j] + arr[i];
/* Pick maximum of
all msis values */
for ( i = 0; i < n; i++ )
if ( max < msis[i] )
max = msis[i];
return max;
}
// Driver Code
int main()
{
int arr[] = {1, 101, 2, 3, 100, 4, 5};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Sum of maximum sum increasing "
"subsequence is " << maxSumIS( arr, n ) << endl;
return 0;
}
// This is code is contributed by rathbhupendra
C
/* Dynamic Programming implementation
of Maximum Sum Increasing Subsequence
(MSIS) problem */
#include<stdio.h>
/* maxSumIS() returns the maximum
sum of increasing subsequence
in arr[] of size n */
int maxSumIS(int arr[], int n)
{
int i, j, max = 0;
int msis[n];
/* Initialize msis values
for all indexes */
for ( i = 0; i < n; i++ )
msis[i] = arr[i];
/* Compute maximum sum values
in bottom up manner */
for ( i = 1; i < n; i++ )
for ( j = 0; j < i; j++ )
if (arr[i] > arr[j] &&
msis[i] < msis[j] + arr[i])
msis[i] = msis[j] + arr[i];
/* Pick maximum of
all msis values */
for ( i = 0; i < n; i++ )
if ( max < msis[i] )
max = msis[i];
return max;
}
// Driver Code
int main()
{
int arr[] = {1, 101, 2, 3, 100, 4, 5};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Sum of maximum sum increasing "
"subsequence is %d\n",
maxSumIS( arr, n ) );
return 0;
}
Java
/* Dynamic Programming Java
implementation of Maximum Sum
Increasing Subsequence (MSIS)
problem */
class GFG
{
/* maxSumIS() returns the
maximum sum of increasing
subsequence in arr[] of size n */
static int maxSumIS(int arr[], int n)
{
int i, j, max = 0;
int msis[] = new int[n];
/* Initialize msis values
for all indexes */
for (i = 0; i < n; i++)
msis[i] = arr[i];
/* Compute maximum sum values
in bottom up manner */
for (i = 1; i < n; i++)
for (j = 0; j < i; j++)
if (arr[i] > arr[j] &&
msis[i] < msis[j] + arr[i])
msis[i] = msis[j] + arr[i];
/* Pick maximum of all
msis values */
for (i = 0; i < n; i++)
if (max < msis[i])
max = msis[i];
return max;
}
// Driver code
public static void main(String args[])
{
int arr[] = new int[]{1, 101, 2, 3, 100, 4, 5};
int n = arr.length;
System.out.println("Sum of maximum sum "+
"increasing subsequence is "+
maxSumIS(arr, n));
}
}
// This code is contributed
// by Rajat Mishra
Python3
# Dynamic Programming based Python
# implementation of Maximum Sum
# Increasing Subsequence (MSIS)
# problem
# maxSumIS() returns the maximum
# sum of increasing subsequence
# in arr[] of size n
def maxSumIS(arr, n):
max = 0
msis = [0 for x in range(n)]
# Initialize msis values
# for all indexes
for i in range(n):
msis[i] = arr[i]
# Compute maximum sum
# values in bottom up manner
for i in range(1, n):
for j in range(i):
if (arr[i] > arr[j] and
msis[i] < msis[j] + arr[i]):
msis[i] = msis[j] + arr[i]
# Pick maximum of
# all msis values
for i in range(n):
if max < msis[i]:
max = msis[i]
return max
# Driver Code
arr = [1, 101, 2, 3, 100, 4, 5]
n = len(arr)
print("Sum of maximum sum increasing " +
"subsequence is " +
str(maxSumIS(arr, n)))
# This code is contributed
# by Bhavya Jain
C#
// Dynamic Programming C# implementation
// of Maximum Sum Increasing Subsequence
// (MSIS) problem
using System;
class GFG {
// maxSumIS() returns the
// maximum sum of increasing
// subsequence in arr[] of size n
static int maxSumIS( int []arr, int n )
{
int i, j, max = 0;
int []msis = new int[n];
/* Initialize msis values
for all indexes */
for ( i = 0; i < n; i++ )
msis[i] = arr[i];
/* Compute maximum sum values
in bottom up manner */
for ( i = 1; i < n; i++ )
for ( j = 0; j < i; j++ )
if ( arr[i] > arr[j] &&
msis[i] < msis[j] + arr[i])
msis[i] = msis[j] + arr[i];
/* Pick maximum of all
msis values */
for ( i = 0; i < n; i++ )
if ( max < msis[i] )
max = msis[i];
return max;
}
// Driver Code
public static void Main()
{
int []arr = new int[]{1, 101, 2, 3, 100, 4, 5};
int n = arr.Length;
Console.WriteLine("Sum of maximum sum increasing "+
" subsequence is "+
maxSumIS(arr, n));
}
}
// This code is contributed by Sam007
PHP
<?php
// Dynamic Programming implementation
// of Maximum Sum Increasing
// Subsequence (MSIS) problem
// maxSumIS() returns the maximum
// sum of increasing subsequence
// in arr[] of size n
function maxSumIS($arr, $n)
{
$max = 0;
$msis= array($n);
// Initialize msis values
// for all indexes
for($i = 0; $i < $n; $i++ )
$msis[$i] = $arr[$i];
// Compute maximum sum values
// in bottom up manner
for($i = 1; $i < $n; $i++)
for($j = 0; $j < $i; $j++)
if ($arr[$i] > $arr[$j] &&
$msis[$i] < $msis[$j] + $arr[$i])
$msis[$i] = $msis[$j] + $arr[$i];
// Pick maximum of all msis values
for($i = 0;$i < $n; $i++ )
if ($max < $msis[$i] )
$max = $msis[$i];
return $max;
}
// Driver Code
$arr = array(1, 101, 2, 3, 100, 4, 5);
$n = count($arr);
echo "Sum of maximum sum increasing subsequence is "
.maxSumIS( $arr, $n );
// This code is contributed by Sam007
?>
Javascript
<script>
// Dynamic Programming implementation
// of Maximum Sum Increasing Subsequence
// (MSIS) problem
// maxSumIS() returns the maximum
// sum of increasing subsequence
// in arr[] of size n
function maxSumIS(arr, n)
{
let i, j, max = 0;
let msis = new Array(n);
// Initialize msis values
// for all indexes
for(i = 0; i < n; i++)
msis[i] = arr[i];
// Compute maximum sum values
// in bottom up manner
for(i = 1; i < n; i++)
for(j = 0; j < i; j++)
if (arr[i] > arr[j] &&
msis[i] < msis[j] + arr[i])
msis[i] = msis[j] + arr[i];
// Pick maximum of
// all msis values
for(i = 0; i < n; i++)
if (max < msis[i])
max = msis[i];
return max;
}
// Driver Code
let arr = [ 1, 101, 2, 3, 100, 4, 5 ];
let n = arr.length;
document.write("Sum of maximum sum increasing " +
"subsequence is " + maxSumIS(arr, n));
// This code is contributed by rishavmahato348
</script>
Producción
Sum of maximum sum increasing subsequence is 106
Complejidad de tiempo: O(n^2)
Complejidad de espacio O(n)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA