Dada una array de N enteros positivos. La tarea es encontrar la suma de la subsecuencia decreciente de suma máxima (MSDS) de la array dada de modo que los enteros en la subsecuencia se clasifiquen en orden decreciente.
Ejemplos :
Entrada: arr[] = {5, 4, 100, 3, 2, 101, 1}
Salida: 106
100 + 3 + 2 + 1 = 106
Entrada: arr[] = {10, 5, 4, 3}
Salida: 22
10 + 5 + 4 + 3 = 22
Este problema es una variación del problema de la subsecuencia decreciente más larga . La subestructura óptima para el problema anterior será:
Sea arr[0..n-1] la array de entrada y MSDS[i] sea la suma máxima de la MSDS que termina en el índice i tal que arr[i] es el último elemento de la MSDS.
Entonces, MSDS[i] se puede escribir como:
MSDS[i] = a[i] + max( MSDS[j] ) donde i > j > 0 y arr[j] > arr[i] o,
MSDS[i] = a[i], si no existe tal j .
Para encontrar la MSDS para una array dada, necesitamos devolver max(MSDS[i]) donde n > i > 0.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP code to return the maximum sum
// of decreasing subsequence in arr[]
#include <bits/stdc++.h>
using namespace std;
// function to return the maximum
// sum of decreasing subsequence
// in arr[]
int maxSumDS(int arr[], int n)
{
int i, j, max = 0;
int MSDS[n];
// Initialize msds values
// for all indexes
for (i = 0; i < n; i++)
MSDS[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] && MSDS[i] < MSDS[j] + arr[i])
MSDS[i] = MSDS[j] + arr[i];
// Pick maximum of all msds values
for (i = 0; i < n; i++)
if (max < MSDS[i])
max = MSDS[i];
return max;
}
// Driver Code
int main()
{
int arr[] = { 5, 4, 100, 3, 2, 101, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Sum of maximum sum decreasing subsequence is: "
<< maxSumDS(arr, n);
return 0;
}
Java
// Java code to return the maximum sum
// of decreasing subsequence in arr[]
import java.io.*;
import java.lang.*;
class GfG {
// function to return the maximum
// sum of decreasing subsequence
// in arr[]
public static int maxSumDS(int arr[], int n)
{
int i, j, max = 0;
int[] MSDS = new int[n];
// Initialize msds values
// for all indexes
for (i = 0; i < n; i++)
MSDS[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] &&
MSDS[i] < MSDS[j] + arr[i])
MSDS[i] = MSDS[j] + arr[i];
// Pick maximum of all msds values
for (i = 0; i < n; i++)
if (max < MSDS[i])
max = MSDS[i];
return max;
}
// Driver Code
public static void main(String argc[])
{
int arr[] = { 5, 4, 100, 3, 2, 101, 1 };
int n = 7;
System.out.println("Sum of maximum sum"
+ " decreasing subsequence is: "
+ maxSumDS(arr, n));
}
}
// This code os contributed by Sagar Shukla.
Python3
# Python3 code to return the maximum sum
# of decreasing subsequence in arr[]
# Function to return the maximum
# sum of decreasing subsequence
# in arr[]
def maxSumDS(arr, n):
i, j, max = (0, 0, 0)
MSDS=[0 for i in range(n)]
# Initialize msds values
# for all indexes
for i in range(n):
MSDS[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
MSDS[i] < MSDS[j] + arr[i]):
MSDS[i] = MSDS[j] + arr[i]
# Pick maximum of all msds values
for i in range(n):
if (max < MSDS[i]):
max = MSDS[i]
return max
if __name__ == "__main__":
arr=[5, 4, 100, 3,
2, 101, 1]
n=len(arr)
print("Sum of maximum sum decreasing subsequence is: ",
maxSumDS(arr, n))
# This code is contributed by Rutvik_56
C#
// C# code to return the
// maximum sum of decreasing
// subsequence in arr[]
using System;
class GFG
{
// function to return the
// maximum sum of decreasing
// subsequence in arr[]
public static int maxSumDS(int []arr,
int n)
{
int i, j, max = 0;
int[] MSDS = new int[n];
// Initialize msds values
// for all indexes
for (i = 0; i < n; i++)
MSDS[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] &&
MSDS[i] < MSDS[j] + arr[i])
MSDS[i] = MSDS[j] + arr[i];
// Pick maximum of
// all msds values
for (i = 0; i < n; i++)
if (max < MSDS[i])
max = MSDS[i];
return max;
}
// Driver Code
static public void Main ()
{
int []arr = {5, 4, 100,
3, 2, 101, 1};
int n = 7;
Console.WriteLine("Sum of maximum sum" +
" decreasing subsequence is: " +
maxSumDS(arr, n));
}
}
// This code is contributed by m_kit
PHP
<?php
// PHP code to return the maximum sum
// of decreasing subsequence in arr[]
// function to return the maximum
// sum of decreasing subsequence
// in arr[]
function maxSumDS($arr, $n)
{
$i; $j; $max = 0;
$MSDS = array();
// Initialize msds values
// for all indexes
for ($i = 0; $i < $n; $i++)
$MSDS[$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] &&
$MSDS[$i] < $MSDS[$j] + $arr[$i])
$MSDS[$i] = $MSDS[$j] + $arr[$i];
// Pick maximum of
// all msds values
for ($i = 0; $i < $n; $i++)
if ($max < $MSDS[$i])
$max = $MSDS[$i];
return $max;
}
// Driver Code
$arr = array (5, 4, 100,
3, 2, 101, 1 );
$n = sizeof($arr);
echo "Sum of maximum sum decreasing " .
"subsequence is: ",
maxSumDS($arr, $n);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript code to return the
// maximum sum of decreasing
// subsequence in arr[]
// function to return the
// maximum sum of decreasing
// subsequence in arr[]
function maxSumDS(arr, n)
{
let i, j, max = 0;
let MSDS = new Array(n);
// Initialize msds values
// for all indexes
for (i = 0; i < n; i++)
MSDS[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] &&
MSDS[i] < MSDS[j] + arr[i])
MSDS[i] = MSDS[j] + arr[i];
// Pick maximum of
// all msds values
for (i = 0; i < n; i++)
if (max < MSDS[i])
max = MSDS[i];
return max;
}
let arr = [5, 4, 100, 3, 2, 101, 1];
let n = 7;
document.write("Sum of maximum sum" +
" decreasing subsequence is: " +
maxSumDS(arr, n));
// This code is contributed by suresh07.
</script>
Salida :
Sum of maximum sum decreasing subsequence is: 106
Complejidad temporal: O(N 2 )
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por aganjali10 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA