Dada una array arr[] , la tarea es encontrar la suma máxima de todos los elementos que no forman parte de la subsecuencia creciente más larga.
Ejemplos:
Entrada: arr[] = {4, 6, 1, 2, 3, 8}
Salida: 10
Explicación:
Los elementos son 4 y 6Entrada: arr[] = {5, 4, 3, 2, 1}
Salida: 14
Explicación:
Los elementos son 5, 4, 3, 2
Acercarse:
- La idea es encontrar la subsecuencia creciente más larga con la suma mínima y luego restarla de la suma de todos los elementos.
- Para hacer esto, usaremos el concepto de LIS usando Programación Dinámica y almacenaremos la suma junto con la longitud de las subsecuencias y actualizaremos la suma mínima en consecuencia.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find the Maximum sum of
// all elements which are not a part of
// longest increasing sub sequence
#include <bits/stdc++.h>
using namespace std;
// Function to find maximum sum
int findSum(int* arr, int n)
{
int totalSum = 0;
// Find total sum of array
for (int i = 0; i < n; i++) {
totalSum += arr[i];
}
// Maintain a 2D array
int dp[2][n];
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
dp[1][i] = arr[i];
}
// Update the dp array along
// with sum in the second row
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j]) {
// In case of greater length
// Update the length along
// with sum
if (dp[0][i] < dp[0][j] + 1) {
dp[0][i] = dp[0][j] + 1;
dp[1][i] = dp[1][j]
+ arr[i];
}
// In case of equal length
// find length update length
// with minimum sum
else if (dp[0][i]
== dp[0][j] + 1) {
dp[1][i]
= min(dp[1][i],
dp[1][j]
+ arr[i]);
}
}
}
}
int maxm = 0;
int subtractSum = 0;
// Find the sum that need to
// be subtracted from total sum
for (int i = 0; i < n; i++) {
if (dp[0][i] > maxm) {
maxm = dp[0][i];
subtractSum = dp[1][i];
}
else if (dp[0][i] == maxm) {
subtractSum = min(subtractSum,
dp[1][i]);
}
}
// Return the sum
return totalSum - subtractSum;
}
// Driver code
int main()
{
int arr[] = { 4, 6, 1, 2, 3, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findSum(arr, n);
return 0;
}
Java
// Java program to find the Maximum sum of
// all elements which are not a part of
// longest increasing sub sequence
class GFG{
// Function to find maximum sum
static int findSum(int []arr, int n)
{
int totalSum = 0;
// Find total sum of array
for(int i = 0; i < n; i++)
{
totalSum += arr[i];
}
// Maintain a 2D array
int [][]dp = new int[2][n];
for(int i = 0; i < n; i++)
{
dp[0][i] = 1;
dp[1][i] = arr[i];
}
// Update the dp array along
// with sum in the second row
for(int i = 1; i < n; i++)
{
for(int j = 0; j < i; j++)
{
if (arr[i] > arr[j])
{
// In case of greater length
// Update the length along
// with sum
if (dp[0][i] < dp[0][j] + 1)
{
dp[0][i] = dp[0][j] + 1;
dp[1][i] = dp[1][j] + arr[i];
}
// In case of equal length
// find length update length
// with minimum sum
else if (dp[0][i] == dp[0][j] + 1)
{
dp[1][i] = Math.min(dp[1][i],
dp[1][j] + arr[i]);
}
}
}
}
int maxm = 0;
int subtractSum = 0;
// Find the sum that need to
// be subtracted from total sum
for(int i = 0; i < n; i++)
{
if (dp[0][i] > maxm)
{
maxm = dp[0][i];
subtractSum = dp[1][i];
}
else if (dp[0][i] == maxm)
{
subtractSum = Math.min(subtractSum, dp[1][i]);
}
}
// Return the sum
return totalSum - subtractSum;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 4, 6, 1, 2, 3, 8 };
int n = arr.length;
System.out.print(findSum(arr, n));
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 program to find the maximum sum # of all elements which are not a part of # longest increasing sub sequence # Function to find maximum sum def findSum(arr, n): totalSum = 0 # Find total sum of array for i in range(n): totalSum += arr[i] # Maintain a 2D array dp = [[0] * n for i in range(2)] for i in range(n): dp[0][i] = 1 dp[1][i] = arr[i] # Update the dp array along # with sum in the second row for i in range(1, n): for j in range(i): if (arr[i] > arr[j]): # In case of greater length # update the length along # with sum if (dp[0][i] < dp[0][j] + 1): dp[0][i] = dp[0][j] + 1 dp[1][i] = dp[1][j] + arr[i] # In case of equal length # find length update length # with minimum sum elif (dp[0][i] == dp[0][j] + 1): dp[1][i] = min(dp[1][i], dp[1][j] + arr[i]) maxm = 0 subtractSum = 0 # Find the sum that need to # be subtracted from total sum for i in range(n): if (dp[0][i] > maxm): maxm = dp[0][i] subtractSum = dp[1][i] elif (dp[0][i] == maxm): subtractSum = min(subtractSum, dp[1][i]) # Return the sum return totalSum - subtractSum # Driver code arr = [ 4, 6, 1, 2, 3, 8 ] n = len(arr) print(findSum(arr, n)) # This code is contributed by himanshu77
C#
// C# program to find the Maximum sum of
// all elements which are not a part of
// longest increasing sub sequence
using System;
class GFG{
// Function to find maximum sum
static int findSum(int []arr, int n)
{
int totalSum = 0;
// Find total sum of array
for(int i = 0; i < n; i++)
{
totalSum += arr[i];
}
// Maintain a 2D array
int [,]dp = new int[2, n];
for(int i = 0; i < n; i++)
{
dp[0, i] = 1;
dp[1, i] = arr[i];
}
// Update the dp array along
// with sum in the second row
for(int i = 1; i < n; i++)
{
for(int j = 0; j < i; j++)
{
if (arr[i] > arr[j])
{
// In case of greater length
// Update the length along
// with sum
if (dp[0, i] < dp[0, j] + 1)
{
dp[0, i] = dp[0, j] + 1;
dp[1, i] = dp[1, j] + arr[i];
}
// In case of equal length
// find length update length
// with minimum sum
else if (dp[0, i] == dp[0, j] + 1)
{
dp[1, i] = Math.Min(dp[1, i],
dp[1, j] + arr[i]);
}
}
}
}
int maxm = 0;
int subtractSum = 0;
// Find the sum that need to
// be subtracted from total sum
for(int i = 0; i < n; i++)
{
if (dp[0, i] > maxm)
{
maxm = dp[0, i];
subtractSum = dp[1, i];
}
else if (dp[0, i] == maxm)
{
subtractSum = Math.Min(subtractSum, dp[1, i]);
}
}
// Return the sum
return totalSum - subtractSum;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 4, 6, 1, 2, 3, 8 };
int n = arr.Length;
Console.Write(findSum(arr, n));
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript program to find the Maximum sum of
// all elements which are not a part of
// longest increasing sub sequence
// Function to find maximum sum
function findSum(arr, n)
{
var totalSum = 0;
// Find total sum of array
for(var i = 0; i < n; i++)
{
totalSum += arr[i];
}
// Maintain a 2D array
var dp = Array.from(Array(2), () => Array(n));
for(var i = 0; i < n; i++)
{
dp[0][i] = 1;
dp[1][i] = arr[i];
}
// Update the dp array along
// with sum in the second row
for(var i = 1; i < n; i++)
{
for(var j = 0; j < i; j++)
{
if (arr[i] > arr[j])
{
// In case of greater length
// Update the length along
// with sum
if (dp[0][i] < dp[0][j] + 1)
{
dp[0][i] = dp[0][j] + 1;
dp[1][i] = dp[1][j] + arr[i];
}
// In case of equal length
// find length update length
// with minimum sum
else if (dp[0][i] == dp[0][j] + 1)
{
dp[1][i] = Math.min(dp[1][i],
dp[1][j] + arr[i]);
}
}
}
}
var maxm = 0;
var subtractSum = 0;
// Find the sum that need to
// be subtracted from total sum
for(var i = 0; i < n; i++)
{
if (dp[0][i] > maxm)
{
maxm = dp[0][i];
subtractSum = dp[1][i];
}
else if (dp[0][i] == maxm)
{
subtractSum = Math.min(subtractSum,
dp[1][i]);
}
}
// Return the sum
return totalSum - subtractSum;
}
// Driver code
var arr = [ 4, 6, 1, 2, 3, 8 ];
var n = arr.length;
document.write( findSum(arr, n));
// This code is contributed by rrrtnx
</script>
Producción:
10
Complejidad de tiempo: O(N 2 ) donde N es la longitud de la array arr[]
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por AmanGupta65 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA