Subsecuencia más pequeña con suma de diferencia absoluta de elementos consecutivos maximizada

Dada una array arr[] de longitud N , que contiene valores en el rango [1, N] , la tarea es encontrar una subsecuencia s ₁ , s ₂ , …, s _k tal que
$\\ Sum = \mid s1 - s2 \mid + \mid s2 - s3 \mid + ... + \mid s_{k-1} - s_{k} \mid$
esté maximizada . En caso de múltiples subsecuencias que tengan la suma máxima posible, imprima la más pequeña.

Entrada: N = 3, P = {3, 2, 1}
Salida: K = 2, S = {3, 1}
Explicación:
Suma máxima posible = 2
Subsecuencias {3, 2, 1} y {3, 1} logra esa suma
Por lo tanto, la subsecuencia {3, 1} se considera de menor longitud.
Entrada: N = 4, P = {1, 3, 4, 2}
Salida: K = 3, S = {1, 4, 2}
Explicación:
Suma máxima posible = 5
Subsecuencias {1, 3, 4, 2} y {1, 4, 2} logra esa suma.
Por lo tanto, la subsecuencia {1, 4, 2} se considera de menor longitud.

Enfoque ingenuo:
Genere todas las subsecuencias de longitud >= 2 y calcule sus respectivas sumas . Mantenga un registro de la suma máxima obtenida para cualquier subsecuencia. En el caso de múltiples subsecuencias que tengan la suma máxima, siga actualizando la longitud mínima y mantenga esa subsecuencia. Finalmente imprima la subsecuencia.
Complejidad de tiempo: O(2 ^N )
Enfoque eficiente:
Hay algunas observaciones clave que nos ayudarán a continuar:

La suma máxima se obtendrá cuando se consideren todos los elementos de la permutación.
Por ejemplo:

N = 4, P = [1, 3, 4, 2]
Suma máxima = | 1 – 3 | + | 3 – 4 | + | 4 – 2 | = 2 + 1 + 2 = 5
Aquí, la longitud es N y la subsecuencia requerida es la permutación P misma.

Ahora que conocemos la suma máxima posible, el objetivo es minimizar la longitud de la subsecuencia sin afectar esta suma máxima.
Para una subsecuencia monótonamente creciente o decreciente, la suma máxima se puede lograr considerando solo el primer y el último elemento, por ejemplo:

S = [1, 3, 5, 7]
Suma máxima = | 1 – 3 | + | 3 – 5 | + | 5 – 7 | = 2 + 2 + 2 = 6, K = 4
Considerando solo el primer y último elemento,
S = [1, 7]
Max sum = | 1 – 7 | = 6, K = 2

De esta manera, la longitud de la subsecuencia se puede reducir sin afectar la suma máxima .
Por lo tanto, de la array dada, siga extrayendo los puntos finales de subsecuencias monótonamente crecientes o decrecientes, y agréguelos a la subsecuencia de la siguiente manera:

El primer y último elemento de la permutación son puntos finales predeterminados

Un elemento P[ i ] es un punto final monótonamente creciente si P[ i – 1 ] < P[ i ] > P[ i + 1 ]

Un elemento P[ i ] es un punto final monótonamente decreciente si P[ i – 1 ] > P[ i ] < P[ i + 1 ]

La subsecuencia así obtenida tendrá suma máxima y longitud mínima.
A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to find
// smallest subsequence
// with sum of absolute
// difference of consecutive
// elements maximized
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the smallest
// subsequence and its sum
void getSubsequence(vector<int>& arr,
                    int n)
{
    // Final subsequence
    vector<int> req;
 
    // First element is
    // a default endpoint
    req.push_back(arr[0]);
 
    // Iterating through the array
    for (int i = 1; i < n - 1; i++) {
 
        // Check for monotonically
        // increasing endpoint
        if (arr[i] > arr[i + 1]
            && arr[i] > arr[i - 1])
            req.push_back(arr[i]);
 
        // Check for monotonically
        // decreasing endpoint
        else if (arr[i] < arr[i + 1]
                 && arr[i] < arr[i - 1])
            req.push_back(arr[i]);
    }
 
    // Last element is
    // a default endpoint
    req.push_back(arr[n - 1]);
 
    // Length of final subsequence
    cout << req.size() << endl;
 
    // Print the subsequence
    for (auto x : req)
        cout << x << " ";
}
 
// Driver Program
int main()
{
    vector<int> arr = { 1, 2, 5, 3,
                        6, 7, 4 };
    int n = arr.size();
    getSubsequence(arr, n);
 
    return 0;
}

Java

// Java program to find smallest
// subsequence with sum of absolute
// difference of consecutive
// elements maximized
import java.util.*;
 
class GFG{
 
// Function to print the smallest
// subsequence and its sum
static void getSubsequence(int []arr, int n)
{
     
    // Final subsequence
    Vector<Integer> req = new Vector<Integer>();
 
    // First element is
    // a default endpoint
    req.add(arr[0]);
 
    // Iterating through the array
    for(int i = 1; i < n - 1; i++)
    {
         
       // Check for monotonically
       // increasing endpoint
       if (arr[i] > arr[i + 1] &&
           arr[i] > arr[i - 1])
           req.add(arr[i]);
            
       // Check for monotonically
       // decreasing endpoint
       else if (arr[i] < arr[i + 1] &&
                arr[i] < arr[i - 1])
           req.add(arr[i]);
    }
 
    // Last element is
    // a default endpoint
    req.add(arr[n - 1]);
 
    // Length of final subsequence
    System.out.print(req.size() + "\n");
 
    // Print the subsequence
    for(int x : req)
       System.out.print(x + " ");
}
 
// Driver code
public static void main(String[] args)
{
    int []arr = { 1, 2, 5, 3,
                  6, 7, 4 };
    int n = arr.length;
     
    getSubsequence(arr, n);
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program to find smallest
# subsequence with sum of absolute
# difference of consecutive
# elements maximized
 
# Function to print the smallest
# subsequence and its sum
def getSubsequence(arr, n):
     
    # Final subsequence
    req = []
     
    # First element is
    # a default endpoint
    req.append(arr[0])
     
    # Iterating through the array
    for i in range(1, n - 1):
         
        # Check for monotonically
        # increasing endpoint
        if (arr[i] > arr[i + 1] and
            arr[i] > arr[i - 1]):
            req.append(arr[i])
        
        # Check for monotonically
        # decreasing endpoint
        elif (arr[i] < arr[i + 1] and
              arr[i] < arr[i - 1]):
            req.append(arr[i]);
             
    # Last element is
    # a default endpoint
    req.append(arr[n - 1]);
 
    # Length of final subsequence
    print(len(req))
 
    # Print the subsequence
    for x in req:
        print(x, end = ' ')
 
# Driver code
if __name__=='__main__':
     
    arr = [ 1, 2, 5, 3, 6, 7, 4 ]
    n = len(arr)
     
    getSubsequence(arr, n)
 
# This code is contributed by rutvik_56

C#

// C# program to find smallest
// subsequence with sum of absolute
// difference of consecutive
// elements maximized
using System;
using System.Collections.Generic;
 
class GFG{
  
// Function to print the smallest
// subsequence and its sum
static void getSubsequence(int []arr, int n)
{
      
    // Final subsequence
    List<int> req = new List<int>();
  
    // First element is
    // a default endpoint
    req.Add(arr[0]);
  
    // Iterating through the array
    for(int i = 1; i < n - 1; i++)
    {
          
       // Check for monotonically
       // increasing endpoint
       if (arr[i] > arr[i + 1] &&
           arr[i] > arr[i - 1])
           req.Add(arr[i]);
             
       // Check for monotonically
       // decreasing endpoint
       else if (arr[i] < arr[i + 1] &&
                arr[i] < arr[i - 1])
           req.Add(arr[i]);
    }
  
    // Last element is
    // a default endpoint
    req.Add(arr[n - 1]);
  
    // Length of readonly subsequence
    Console.Write(req.Count + "\n");
  
    // Print the subsequence
    foreach(int x in req)
       Console.Write(x + " ");
}
  
// Driver code
public static void Main(String[] args)
{
    int []arr = { 1, 2, 5, 3,
                  6, 7, 4 };
    int n = arr.Length;
      
    getSubsequence(arr, n);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
        // JavaScript code for the above approach
 
        // Function to print the smallest
        // subsequence and its sum
        function getSubsequence(arr, n)
        {
         
            // Final subsequence
            let req = [];
 
            // First element is
            // a default endpoint
            req.push(arr[0]);
 
            // Iterating through the array
            for (let i = 1; i < n - 1; i++) {
 
                // Check for monotonically
                // increasing endpoint
                if (arr[i] > arr[i + 1]
                    && arr[i] > arr[i - 1])
                    req.push(arr[i]);
 
                // Check for monotonically
                // decreasing endpoint
                else if (arr[i] < arr[i + 1]
                    && arr[i] < arr[i - 1])
                    req.push(arr[i]);
            }
 
            // Last element is
            // a default endpoint
            req.push(arr[n - 1]);
 
            // Length of final subsequence
            document.write(req.length + '<br>');
 
            // Print the subsequence
            for (let x of req)
                document.write(x + " ");
        }
 
        // Driver Program
        let arr = [1, 2, 5, 3,
            6, 7, 4];
        let n = arr.length;
        getSubsequence(arr, n);
 
  // This code is contributed by Potta Lokesh
    </script>

Producción:

5
1 5 3 7 4

Complejidad del tiempo: O(N)

Publicación traducida automáticamente

Artículo escrito por greenindia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta