Impresión de la suma máxima de la subsecuencia creciente

El problema de la subsecuencia creciente de suma máxima es encontrar la subsecuencia de suma máxima de una secuencia dada de modo que todos los elementos de la subsecuencia se ordenen en orden creciente.

Ejemplos: 

Input:  [1, 101, 2, 3, 100, 4, 5]
Output: [1, 2, 3, 100]

Input:  [3, 4, 5, 10]
Output: [3, 4, 5, 10]

Input:  [10, 5, 4, 3]
Output: [10]

Input:  [3, 2, 6, 4, 5, 1]
Output: [3, 4, 5]

En una publicación anterior , hemos discutido el problema de la subsecuencia creciente de suma máxima. Sin embargo, la publicación solo cubría el código relacionado con la búsqueda de la suma máxima de subsecuencias crecientes, pero no con la construcción de subsecuencias. En esta publicación, discutiremos cómo construir la Subsecuencia Creciente de Suma Máxima en sí misma.

Sea arr[0..n-1] la array de entrada. Definimos el vector L tal que L[i] es en sí mismo un vector que almacena la Subsecuencia Creciente de Suma Máxima de arr[0..i] que termina en arr[i]. Por lo tanto, para el índice i, L[i] puede escribirse recursivamente como 

L[0] = {arr[0]}
L[i] = {MaxSum(L[j])} + arr[i] where j < i and arr[j] < arr[i]
     = arr[i], if there is no j such that arr[j] < arr[i]

Por ejemplo, para la array [3, 2, 6, 4, 5, 1], 

L[0]: 3
L[1]: 2
L[2]: 3 6
L[3]: 3 4
L[4]: 3 4 5
L[5]: 1

A continuación se muestra la implementación de la idea anterior: 

/* Dynamic Programming solution to construct
   Maximum Sum Increasing Subsequence */
#include <iostream>
#include <vector>
using namespace std;
 
// Utility function to calculate sum of all
// vector elements
int findSum(vector<int> arr)
{
    int sum = 0;
    for (int i : arr)
        sum += i;
    return sum;
}
 
// Function to construct Maximum Sum Increasing
// Subsequence
void printMaxSumIS(int arr[], int n)
{
    // L[i] - The Maximum Sum Increasing
    // Subsequence that ends with arr[i]
    vector<vector<int> > L(n);
 
    // L[0] is equal to arr[0]
    L[0].push_back(arr[0]);
 
    // start from index 1
    for (int i = 1; i < n; i++) {
        // for every j less than i
        for (int j = 0; j < i; j++) {
            /* L[i] = {MaxSum(L[j])} + arr[i]
            where j < i and arr[j] < arr[i] */
            if ((arr[i] > arr[j])
                && (findSum(L[i]) < findSum(L[j])))
                L[i] = L[j];
        }
 
        // L[i] ends with arr[i]
        L[i].push_back(arr[i]);
 
        // L[i] now stores Maximum Sum Increasing
        // Subsequence of arr[0..i] that ends with
        // arr[i]
    }
 
    vector<int> res = L[0];
 
    // find max
    for (vector<int> x : L)
        if (findSum(x) > findSum(res))
            res = x;
 
    // max will contain result
    for (int i : res)
        cout << i << " ";
    cout << endl;
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 2, 6, 4, 5, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // construct and print Max Sum IS of arr
    printMaxSumIS(arr, n);
 
    return 0;
}

/* Dynamic Programming solution to construct
Maximum Sum Increasing Subsequence */
import java.util.*;
 
class GFG {
 
    // Utility function to calculate sum of all
    // vector elements
    static int findSum(Vector<Integer> arr)
    {
        int sum = 0;
        for (int i : arr)
            sum += i;
        return sum;
    }
 
    // Function to construct Maximum Sum Increasing
    // Subsequence
    static void printMaxSumIs(int[] arr, int n)
    {
 
        // L[i] - The Maximum Sum Increasing
        // Subsequence that ends with arr[i]
        @SuppressWarnings("unchecked")
        Vector<Integer>[] L = new Vector[n];
 
        for (int i = 0; i < n; i++)
            L[i] = new Vector<>();
 
        // L[0] is equal to arr[0]
        L[0].add(arr[0]);
 
        // start from index 1
        for (int i = 1; i < n; i++) {
 
            // for every j less than i
            for (int j = 0; j < i; j++) {
 
                /*
                * L[i] = {MaxSum(L[j])} + arr[i]
                  where j < i and arr[j] < arr[i]
                */
                if ((arr[i] > arr[j])
                    && (findSum(L[i]) < findSum(L[j]))) {
                    for (int k : L[j])
                        if (!L[i].contains(k))
                            L[i].add(k);
                }
            }
 
            // L[i] ends with arr[i]
            L[i].add(arr[i]);
 
            // L[i] now stores Maximum Sum Increasing
            // Subsequence of arr[0..i] that ends with
            // arr[i]
        }
 
        Vector<Integer> res = new Vector<>(L[0]);
        // res = L[0];
 
        // find max
        for (Vector<Integer> x : L)
            if (findSum(x) > findSum(res))
                res = x;
 
        // max will contain result
        for (int i : res)
            System.out.print(i + " ");
        System.out.println();
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 3, 2, 6, 4, 5, 1 };
        int n = arr.length;
 
        // construct and print Max Sum IS of arr
        printMaxSumIs(arr, n);
    }
}
 
// This code is contributed by
// sanjeev2552

# Dynamic Programming solution to construct
# Maximum Sum Increasing Subsequence */
 
# Utility function to calculate sum of all
# vector elements
 
 
def findSum(arr):
 
    summ = 0
    for i in arr:
        summ += i
    return summ
 
# Function to construct Maximum Sum Increasing
# Subsequence
 
 
def printMaxSumIS(arr, n):
 
    # L[i] - The Maximum Sum Increasing
    # Subsequence that ends with arr[i]
    L = [[] for i in range(n)]
 
    # L[0] is equal to arr[0]
    L[0].append(arr[0])
 
    # start from index 1
    for i in range(1, n):
 
        # for every j less than i
        for j in range(i):
 
            # L[i] = {MaxSum(L[j])} + arr[i]
            # where j < i and arr[j] < arr[i]
            if ((arr[i] > arr[j]) and
                    (findSum(L[i]) < findSum(L[j]))):
                for e in L[j]:
                    if e not in L[i]:
                        L[i].append(e)
 
        # L[i] ends with arr[i]
        L[i].append(arr[i])
 
        # L[i] now stores Maximum Sum Increasing
        # Subsequence of arr[0..i] that ends with
        # arr[i]
 
    res = L[0]
 
    # find max
    for x in L:
        if (findSum(x) > findSum(res)):
            res = x
 
    # max will contain result
    for i in res:
        print(i, end=" ")
 
 
# Driver Code
arr = [3, 2, 6, 4, 5, 1]
n = len(arr)
 
# construct and prMax Sum IS of arr
printMaxSumIS(arr, n)
 
# This code is contributed by Mohit Kumar

/* Dynamic Programming solution to construct
Maximum Sum Increasing Subsequence */
using System;
using System.Collections.Generic;
 
class GFG {
 
    // Utility function to calculate sum of all
    // vector elements
    static int findSum(List<int> arr)
    {
        int sum = 0;
        foreach(int i in arr) sum += i;
        return sum;
    }
 
    // Function to construct Maximum Sum Increasing
    // Subsequence
    static void printMaxSumIs(int[] arr, int n)
    {
 
        // L[i] - The Maximum Sum Increasing
        // Subsequence that ends with arr[i]
        List<int>[] L = new List<int>[ n ];
 
        for (int i = 0; i < n; i++)
            L[i] = new List<int>();
 
        // L[0] is equal to arr[0]
        L[0].Add(arr[0]);
 
        // start from index 1
        for (int i = 1; i < n; i++) {
 
            // for every j less than i
            for (int j = 0; j < i; j++) {
 
                /*
                * L[i] = {MaxSum(L[j])} + arr[i]
                where j < i and arr[j] < arr[i]
                */
                if ((arr[i] > arr[j])
                    && (findSum(L[i]) < findSum(L[j]))) {
                    foreach(int k in
                                L[j]) if (!L[i].Contains(k))
                        L[i]
                            .Add(k);
                }
            }
 
            // L[i] ends with arr[i]
            L[i].Add(arr[i]);
 
            // L[i] now stores Maximum Sum Increasing
            // Subsequence of arr[0..i] that ends with
            // arr[i]
        }
 
        List<int> res = new List<int>(L[0]);
        // res = L[0];
 
        // find max
        foreach(List<int> x in L) if (findSum(x)
                                      > findSum(res)) res
            = x;
 
        // max will contain result
        foreach(int i in res) Console.Write(i + " ");
        Console.WriteLine();
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int[] arr = { 3, 2, 6, 4, 5, 1 };
        int n = arr.Length;
 
        // construct and print Max Sum IS of arr
        printMaxSumIs(arr, n);
    }
}
 
// This code is contributed by PrinciRaj1992

<script>
 
/* Dynamic Programming solution to construct
Maximum Sum Increasing Subsequence */
     
    // Utility function to calculate sum of all
    // vector elements
    function findSum(arr)
    {
        let sum = 0;
        for (let i=0;i<arr.length;i++)
            sum += arr[i];
        return sum;
    }
     
    // Function to construct Maximum Sum Increasing
    // Subsequence
    function printMaxSumIs(arr,n)
    {
        // L[i] - The Maximum Sum Increasing
        // Subsequence that ends with arr[i]
         
        let L = new Array(n);
  
        for (let i = 0; i < n; i++)
            L[i] = [];
  
        // L[0] is equal to arr[0]
        L[0].push(arr[0]);
  
        // start from index 1
        for (let i = 1; i < n; i++) {
  
            // for every j less than i
            for (let j = 0; j < i; j++) {
  
                /*
                * L[i] = {MaxSum(L[j])} + arr[i]
                  where j < i and arr[j] < arr[i]
                */
                if ((arr[i] > arr[j])
                    && (findSum(L[i]) < findSum(L[j])))
                    {
                    for (let k=0;k<L[j].length;k++)
                        if (!L[i].includes(L[j][k]))
                            L[i].push(L[j][k]);
                }
            }
  
            // L[i] ends with arr[i]
            L[i].push(arr[i]);
  
            // L[i] now stores Maximum Sum Increasing
            // Subsequence of arr[0..i] that ends with
            // arr[i]
        }
          
        let res = L[0];
        // res = L[0];
      
        // find max
        for (let x=0;x<L.length;x++)
            if (findSum(L[x]) > findSum(res))
                res = L[x];
  
        // max will contain result
        for (let i=0;i<res.length;i++)
            document.write(res[i] + " ");
        document.write("<br>");
    }
     
     // Driver Code
    let arr=[3, 2, 6, 4, 5, 1];
    let n = arr.length;
     
    // construct and print Max Sum IS of arr
    printMaxSumIs(arr, n);
     
 
// This code is contributed by unknown2108
 
</script>

3 4 5

 Podemos optimizar la solución de DP anterior eliminando la función findSum(). En cambio, podemos mantener otro vector/array para almacenar la suma de la subsecuencia creciente de suma máxima que termina con arr[i]. La implementación se puede ver aquí .

La complejidad temporal de la solución de programación dinámica anterior es O(n ² ). 
El espacio auxiliar utilizado por el programa es O(n ² ).

Enfoque 2: ( Uso de la programación dinámica Uso del espacio O(N)

El enfoque anterior cubría cómo construir una Subsecuencia Creciente de Suma Máxima en el tiempo O(N ² ) y el espacio O(N ² ). En este enfoque, optimizaremos la complejidad del espacio y construiremos la subsecuencia creciente de suma máxima en el tiempo O(N ² ) y el espacio O(N).

• Sea arr[0..n-1] la array de entrada.
• Definimos un vector de pares L tal que L[i] primero almacena la Subsecuencia Creciente de Suma Máxima de arr[0..i] que termina en arr[i] y L[i].segundo almacena el índice del elemento anterior utilizado para generar la suma.
• Como el primer elemento no tiene ningún elemento anterior, su índice sería -1 en L[0].

Por ejemplo, 

array = [3, 2, 6, 4, 5, 1]

L[0]: {3, -1}
L[1]: {2,  1}
L[2]: {9,  0}
L[3]: {7, 0}
L[4]: {12, 3}
L[5]: {1, 5}

Como podemos ver arriba, el valor de la Subsecuencia Creciente de Suma Máxima es 12. Para construir la Subsecuencia real usaremos el índice almacenado en L[i].segundo. Los pasos para construir la Subsecuencia se muestran a continuación: 

• En un resultado vectorial, almacene el valor del elemento donde se encontró la Subsecuencia creciente de suma máxima (es decir, en currIndex = 4). Entonces, en el vector de resultados, agregaremos arr[currIndex].
• Actualice currIndex a L[currIndex].segundo y repita el paso 1 hasta que currIndex no sea -1 o no cambie (es decir, currIndex == índice anterior).
• Muestre los elementos del vector de resultado en orden inverso.

A continuación se muestra la implementación de la idea anterior: 

/* Dynamic Programming solution to construct
Maximum Sum Increasing Subsequence */
#include <bits/stdc++.h>
using namespace std;
 
// Function to construct and print the Maximum Sum
// Increasing Subsequence
void constructMaxSumIS(vector<int> arr, int n)
{
    // L[i] stores the value of Maximum Sum Increasing
    // Subsequence that ends with arr[i] and the index of
    // previous element used to construct the Subsequence
    vector<pair<int, int> > L(n);
 
    int index = 0;
    for (int i : arr) {
        L[index] = { i, index };
        index++;
    }
 
    // Set L[0].second equal to -1
    L[0].second = -1;
 
    // start from index 1
    for (int i = 1; i < n; i++) {
        // for every j less than i
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]
                and L[i].first < arr[i] + L[j].first) {
                L[i].first = arr[i] + L[j].first;
                L[i].second = j;
            }
        }
    }
 
    int maxi = INT_MIN, currIndex, track = 0;
 
    for (auto p : L) {
        if (p.first > maxi) {
            maxi = p.first;
            currIndex = track;
        }
        track++;
    }
 
    // Stores the final Subsequence
    vector<int> result;
 
    // Index of previous element
    // used to construct the Subsequence
    int prevoiusIndex;
 
    while (currIndex >= 0) {
        result.push_back(arr[currIndex]);
        prevoiusIndex = L[currIndex].second;
 
        if (currIndex == prevoiusIndex)
            break;
 
        currIndex = prevoiusIndex;
    }
 
    for (int i = result.size() - 1; i >= 0; i--)
        cout << result[i] << " ";
}
 
// Driver Code
int main()
{
    vector<int> arr = { 1, 101, 2, 3, 100, 4, 5 };
    int n = arr.size();
 
    // Function call
    constructMaxSumIS(arr, n);
 
    return 0;
}

// Dynamic Programming solution to construct
// Maximum Sum Increasing Subsequence
import java.util.*;
import java.awt.Point;
 
class GFG{
     
// Function to construct and print the Maximum Sum
// Increasing Subsequence
static void constructMaxSumIS(List<Integer> arr, int n)
{
     
    // L.get(i) stores the value of Maximum Sum Increasing
    // Subsequence that ends with arr.get(i) and the index of
    // previous element used to construct the Subsequence
    List<Point> L = new ArrayList<Point>();
 
    int index = 0;
    for(int i : arr)
    {
        L.add(new Point(i, index));
        index++;
    }
 
    // Set L[0].second equal to -1
    L.set(0, new Point(L.get(0).x, -1));
 
    // Start from index 1
    for(int i = 1; i < n; i++)
    {
         
        // For every j less than i
        for(int j = 0; j < i; j++)
        {
            if (arr.get(i) > arr.get(j) &&
                L.get(i).x < arr.get(i) +
                L.get(j).x)
            {
                L.set(i, new Point(arr.get(i) +
                                     L.get(j).x, j));
            }
        }
    }
 
    int maxi = -100000000, currIndex = 0, track = 0;
 
    for(Point p : L)
    {
        if (p.x > maxi)
        {
            maxi = p.x;
            currIndex = track;
        }
        track++;
    }
 
    // Stores the final Subsequence
    List<Integer> result = new ArrayList<Integer>();
 
    // Index of previous element
    // used to construct the Subsequence
    int prevoiusIndex;
 
    while (currIndex >= 0)
    {
        result.add(arr.get(currIndex));
        prevoiusIndex = L.get(currIndex).y;
 
        if (currIndex == prevoiusIndex)
            break;
 
        currIndex = prevoiusIndex;
    }
 
    for(int i = result.size() - 1; i >= 0; i--)
        System.out.print(result.get(i) + " ");
}
 
// Driver Code
public static void main(String []s)
{
    List<Integer> arr = new ArrayList<Integer>();
    arr.add(1);
    arr.add(101);
    arr.add(2);
    arr.add(3);
    arr.add(100);
    arr.add(4);
    arr.add(5);
     
    int n = arr.size();
 
    // Function call
    constructMaxSumIS(arr, n);
}
}
 
// This code is contributed by rutvik_56

# Dynamic Programming solution to construct
# Maximum Sum Increasing Subsequence
import sys
 
# Function to construct and print the Maximum Sum
# Increasing Subsequence
def constructMaxSumIS(arr, n) :
 
    # L[i] stores the value of Maximum Sum Increasing
    # Subsequence that ends with arr[i] and the index of
    # previous element used to construct the Subsequence
    L = []
 
    index = 0
    for i in arr :
        L.append([i, index])
        index += 1
 
    # Set L[0].second equal to -1
    L[0][1] = -1
 
    # start from index 1
    for i in range(1, n) :
       
        # for every j less than i
        for j in range(i) :
            if (arr[i] > arr[j] and L[i][0] < arr[i] + L[j][0]) :
                L[i][0] = arr[i] + L[j][0]
                L[i][1] = j
 
    maxi, currIndex, track = -sys.maxsize, 0, 0
 
    for p in L :
        if (p[0] > maxi) :
            maxi = p[0]
            currIndex = track
     
        track += 1
 
    # Stores the final Subsequence
    result = []
 
    while (currIndex >= 0) :
        result.append(arr[currIndex])
        prevoiusIndex = L[currIndex][1]
 
        if (currIndex == prevoiusIndex) :
            break
 
        currIndex = prevoiusIndex
 
    for i in range(len(result) - 1, -1, -1) :
        print(result[i] , end = " ")
 
 
arr = [ 1, 101, 2, 3, 100, 4, 5 ]
n = len(arr)
 
# Function call
constructMaxSumIS(arr, n)
 
# This code is contributed by divyeshrabadiya07

/* Dynamic Programming solution to construct
Maximum Sum Increasing Subsequence */
using System;
using System.Collections.Generic;
class GFG
{
     
    // Function to construct and print the Maximum Sum
    // Increasing Subsequence
    static void constructMaxSumIS(List<int> arr, int n)
    {
       
        // L[i] stores the value of Maximum Sum Increasing
        // Subsequence that ends with arr[i] and the index of
        // previous element used to construct the Subsequence
        List<Tuple<int, int>> L = new List<Tuple<int, int>>();
      
        int index = 0;
        foreach(int i in arr) {
            L.Add(new Tuple<int, int>(i, index));
            index++;
        }
      
        // Set L[0].second equal to -1
        L[0] = new Tuple<int, int>(L[0].Item1, -1);
      
        // start from index 1
        for (int i = 1; i < n; i++)
        {
           
            // for every j less than i
            for (int j = 0; j < i; j++)
            {
                if (arr[i] > arr[j] &&
                    L[i].Item1 < arr[i] +
                    L[j].Item1)
                {
                    L[i] = new Tuple<int,
                  int>(arr[i] + L[j].Item1, j);
                }
            }
        }
      
        int maxi = Int32.MinValue,
      currIndex = 0, track = 0;
      
        foreach(Tuple<int, int> p in L)
        {
            if (p.Item1 > maxi)
            {
                maxi = p.Item1;
                currIndex = track;
            }
            track++;
        }
      
        // Stores the final Subsequence
        List<int> result = new List<int>();
      
        // Index of previous element
        // used to construct the Subsequence
        int prevoiusIndex;
      
        while (currIndex >= 0)
        {
            result.Add(arr[currIndex]);
            prevoiusIndex = L[currIndex].Item2;
      
            if (currIndex == prevoiusIndex)
                break;
      
            currIndex = prevoiusIndex;
        }
      
        for (int i = result.Count - 1; i >= 0; i--)
            Console.Write(result[i] + " ");
    } 
 
  static void Main()
  {
    List<int> arr = new List<int>(new
                                  int[] { 1, 101, 2, 3, 100, 4, 5 });
    int n = arr.Count;
  
    // Function call
    constructMaxSumIS(arr, n);
  }
}
 
// This code is contributed by divyesh072019

<script>
 
// Dynamic Programming solution to construct
// Maximum Sum Increasing Subsequence
 
// Function to construct and print the Maximum Sum
// Increasing Subsequence
function constructMaxSumIS(arr, n){
 
    // L[i] stores the value of Maximum Sum Increasing
    // Subsequence that ends with arr[i] and the index of
    // previous element used to construct the Subsequence
    let L = []
 
    let index = 0
    for(let i of arr){
        L.push([i, index])
        index += 1
    }
 
    // Set L[0].second equal to -1
    L[0][1] = -1
 
    // start from index 1
    for(let i=1;i<n;i++){
       
        // for every j less than i
        for(let j=0;j<i;j++){
            if (arr[i] > arr[j] && L[i][0] < arr[i] + L[j][0]){
                L[i][0] = arr[i] + L[j][0]
                L[i][1] = j
            }
        }
    }
 
    let maxi = Number.MIN_VALUE, currIndex = 0, track = 0
 
    for(let p of L){
        if (p[0] > maxi){
            maxi = p[0]
            currIndex = track
        }
     
        track += 1
    }
 
    // Stores the final Subsequence
    let result = []
 
    while (currIndex >= 0){
        result.push(arr[currIndex])
        let prevoiusIndex = L[currIndex][1]
 
        if (currIndex == prevoiusIndex)
            break
 
        currIndex = prevoiusIndex
    }
 
    for(let i=result.length - 1;i>=0;i--)
        document.write(result[i] ," ")
}
 
 
let arr = [ 1, 101, 2, 3, 100, 4, 5 ]
let n = arr.length
 
// Function call
constructMaxSumIS(arr, n)
 
// This code is contributed by shinjanpatra
 
</script>

1 2 3 100

Complejidad de tiempo: O(N ² )
Complejidad de espacio: O(N)

Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.