Dada una array arr[] de longitud N que consta de enteros positivos , la tarea es encontrar la subsecuencia creciente más larga que pueden formar los elementos de cualquier extremo de la array.
Ejemplos:
Entrada: N=4 arr[] ={ 1, 4, 2, 3 }
Salida: 1 3 4
Explicación:
Agregue arr[0] a la secuencia. Secuencia = {1}. Array = {4, 2, 3}.
Agregue arr[2] a la secuencia. Secuencia = {1, 3}. Array = {4, 2}.
Agregue arr[0] a la secuencia. Secuencia = {1, 3, 4}. Array = {2}.
Por lo tanto, {1, 3, 4} es la secuencia creciente más larga posible de la array dada.Entrada: N=3 arr[] ={ 4, 1, 3 }
Salida: 3 4
Enfoque: La idea para resolver este problema es utilizar el enfoque de dos punteros . Mantenga una variable, digamos rightmost_element, para el elemento más a la derecha en la secuencia estrictamente creciente. Mantenga dos punteros en los extremos de la array, digamos i y j respectivamente y realice los siguientes pasos hasta que i supere a j o los elementos en ambos extremos sean más pequeños que el elemento más a la derecha :
- Si arr[i] > arr[j]:
- Si arr[j] > rightmost_element: Establezca rightmost_element = arr[j] y disminuya j . Agregue arr[j] a la secuencia.
- Si arr[i] > rightmost_element: Establezca rightmost_element = arr[i] e incremente i . Agregue arr[i] a la secuencia.
- Si arr[i] < arr[j]:
- Si arr[i] > rightmost_element : Establezca rightmost_element = arr[i] e incremente i . Agregue arr[i] a la secuencia.
- Si arr[j] > rightmost_element : Establezca rightmost_element = arr[j] y disminuya j . Agregue arr[j] a la secuencia.
- Si arr[j] = arr[i]:
- Si yo = j:
- Si arr[i]>rightmost_element : agregue arr[i] a la secuencia.
- De lo contrario: verifique los elementos máximos que se pueden agregar desde los dos extremos respectivamente, déjelos ser max_left y max_right respectivamente.
- Si max_left > max_right : agregue todos los elementos que se pueden agregar desde el extremo izquierdo.
- De lo contrario: Agregue todos los elementos que se pueden agregar desde el lado derecho.
- Si yo = j:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
#include <vector>
using namespace std;
// Function to find longest strictly
// increasing sequence using boundary elements
void findMaxLengthSequence(int N, int arr[4])
{
// Maintains rightmost element
// in the sequence
int rightmost_element = -1;
// Pointer to start of array
int i = 0;
// Pointer to end of array
int j = N - 1;
// Stores the required sequence
vector<int> sequence;
// Traverse the array
while (i <= j) {
// If arr[i]>arr[j]
if (arr[i] > arr[j]) {
// If arr[j] is greater than
// rightmost element of the sequence
if (arr[j] > rightmost_element) {
// Push arr[j] into the sequence
sequence.push_back(arr[j]);
// Update rightmost element
rightmost_element = arr[j];
j--;
}
else if (arr[i] > rightmost_element) {
// Push arr[i] into the sequence
sequence.push_back(arr[i]);
// Update rightmost element
rightmost_element = arr[i];
i++;
}
else
break;
}
// If arr[i] < arr[j]
else if (arr[i] < arr[j]) {
// If arr[i] > rightmost element
if (arr[i] > rightmost_element) {
// Push arr[i] into the sequence
sequence.push_back(arr[i]);
// Update rightmost element
rightmost_element = arr[i];
i++;
}
// If arr[j] > rightmost element
else if (arr[j] > rightmost_element) {
// Push arr[j] into the sequence
sequence.push_back(arr[j]);
// Update rightmost element
rightmost_element = arr[j];
j--;
}
else
break;
}
// If arr[i] is equal to arr[j]
else if (arr[i] == arr[j]) {
// If i and j are at the same element
if (i == j) {
// If arr[i] > rightmostelement
if (arr[i] > rightmost_element) {
// Push arr[j] into the sequence
sequence.push_back(arr[i]);
// Update rightmost element
rightmost_element = arr[i];
i++;
}
break;
}
else {
sequence.push_back(arr[i]);
// Traverse array
// from left to right
int k = i + 1;
// Stores the increasing
// sequence from the left end
vector<int> max_left;
// Traverse array from left to right
while (k < j && arr[k] > arr[k - 1]) {
// Push arr[k] to max_left vector
max_left.push_back(arr[k]);
k++;
}
// Traverse the array
// from right to left
int l = j - 1;
// Stores the increasing
// sequence from the right end
vector<int> max_right;
// Traverse array from right to left
while (l > i && arr[l] > arr[l + 1]) {
// Push arr[k] to max_right vector
max_right.push_back(arr[l]);
l--;
}
// If size of max_left is greater
// than max_right
if (max_left.size() > max_right.size())
for (int element : max_left)
// Push max_left elements to
// the original sequence
sequence.push_back(element);
// Otherwise
else
for (int element : max_right)
// Push max_right elements to
// the original sequence
sequence.push_back(element);
break;
}
}
}
// Print the sequence
for (int element : sequence)
printf("%d ", element);
}
// Driver Code
int main()
{
int N = 4;
int arr[] = { 1, 3, 2, 1 };
// Print the longest increasing
// sequence using boundary elements
findMaxLengthSequence(N, arr);
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find longest strictly
// increasing sequence using boundary elements
static void findMaxLengthSequence(int N, int[] arr)
{
// Maintains rightmost element
// in the sequence
int rightmost_element = -1;
// Pointer to start of array
int i = 0;
// Pointer to end of array
int j = N - 1;
// Stores the required sequence
Vector<Integer> sequence = new Vector<Integer>();
// Traverse the array
while (i <= j)
{
// If arr[i]>arr[j]
if (arr[i] > arr[j])
{
// If arr[j] is greater than
// rightmost element of the sequence
if (arr[j] > rightmost_element)
{
// Push arr[j] into the sequence
sequence.add(arr[j]);
// Update rightmost element
rightmost_element = arr[j];
j--;
}
else if (arr[i] > rightmost_element)
{
// Push arr[i] into the sequence
sequence.add(arr[i]);
// Update rightmost element
rightmost_element = arr[i];
i++;
}
else
break;
}
// If arr[i] < arr[j]
else if (arr[i] < arr[j])
{
// If arr[i] > rightmost element
if (arr[i] > rightmost_element)
{
// Push arr[i] into the sequence
sequence.add(arr[i]);
// Update rightmost element
rightmost_element = arr[i];
i++;
}
// If arr[j] > rightmost element
else if (arr[j] > rightmost_element)
{
// Push arr[j] into the sequence
sequence.add(arr[j]);
// Update rightmost element
rightmost_element = arr[j];
j--;
}
else
break;
}
// If arr[i] is equal to arr[j]
else if (arr[i] == arr[j])
{
// If i and j are at the same element
if (i == j)
{
// If arr[i] > rightmostelement
if (arr[i] > rightmost_element)
{
// Push arr[j] into the sequence
sequence.add(arr[i]);
// Update rightmost element
rightmost_element = arr[i];
i++;
}
break;
}
else
{
sequence.add(arr[i]);
// Traverse array
// from left to right
int k = i + 1;
// Stores the increasing
// sequence from the left end
Vector<Integer> max_left = new Vector<Integer>();
// Traverse array from left to right
while (k < j && arr[k] > arr[k - 1])
{
// Push arr[k] to max_left vector
max_left.add(arr[k]);
k++;
}
// Traverse the array
// from right to left
int l = j - 1;
// Stores the increasing
// sequence from the right end
Vector<Integer> max_right = new Vector<Integer>();
// Traverse array from right to left
while (l > i && arr[l] > arr[l + 1])
{
// Push arr[k] to max_right vector
max_right.add(arr[l]);
l--;
}
// If size of max_left is greater
// than max_right
if (max_left.size() > max_right.size())
for(int element : max_left)
// Push max_left elements to
// the original sequence
sequence.add(element);
// Otherwise
else
for(int element : max_right)
// Push max_right elements to
// the original sequence
sequence.add(element);
break;
}
}
}
// Print the sequence
for(int element : sequence)
System.out.print(element + " ");
}
// Driver Code
public static void main(String[] args)
{
int N = 4;
int[] arr = { 1, 3, 2, 1 };
// Print the longest increasing
// sequence using boundary elements
findMaxLengthSequence(N, arr);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program for the above approach # Function to find longest strictly # increasing sequence using boundary elements def findMaxLengthSequence(N, arr): # Maintains rightmost element # in the sequence rightmost_element = -1 # Pointer to start of array i = 0 # Pointer to end of array j = N - 1 # Stores the required sequence sequence = [] # Traverse the array while (i <= j): # If arr[i]>arr[j] if (arr[i] > arr[j]): # If arr[j] is greater than # rightmost element of the sequence if (arr[j] > rightmost_element): # Push arr[j] into the sequence sequence.append(arr[j]) # Update rightmost element rightmost_element = arr[j] j -= 1 elif (arr[i] > rightmost_element): # Push arr[i] into the sequence sequence.append(arr[i]) # Update rightmost element rightmost_element = arr[i] i += 1 else: break # If arr[i] < arr[j] elif (arr[i] < arr[j]): # If arr[i] > rightmost element if (arr[i] > rightmost_element): # Push arr[i] into the sequence sequence.append(arr[i]) # Update rightmost element rightmost_element = arr[i] i += 1 # If arr[j] > rightmost element elif (arr[j] > rightmost_element): # Push arr[j] into the sequence sequence.append(arr[j]) # Update rightmost element rightmost_element = arr[j] j -= 1 else: break # If arr[i] is equal to arr[j] elif (arr[i] == arr[j]): # If i and j are at the same element if (i == j): # If arr[i] > rightmostelement if (arr[i] > rightmost_element): # Push arr[j] into the sequence sequence.append(arr[i]) # Update rightmost element rightmost_element = arr[i] i += 1 break else: sequence.append(arr[i]) # Traverse array # from left to right k = i + 1 # Stores the increasing # sequence from the left end max_left = [] # Traverse array from left to right while (k < j and arr[k] > arr[k - 1]): # Push arr[k] to max_left vector max_left.append(arr[k]) k += 1 # Traverse the array # from right to left l = j - 1 # Stores the increasing # sequence from the right end max_right = [] # Traverse array from right to left while (l > i and arr[l] > arr[l + 1]): # Push arr[k] to max_right vector max_right.append(arr[l]) l -= 1 # If size of max_left is greater # than max_right if (len(max_left) > len(max_right)): for element in max_left: # Push max_left elements to # the original sequence sequence.append(element) # Otherwise else: for element in max_right: # Push max_right elements to # the original sequence sequence.append(element) break # Print the sequence for element in sequence: print(element, end = " ") # Driver Code if __name__ == '__main__': N = 4 arr = [ 1, 3, 2, 1 ] # Print the longest increasing # sequence using boundary elements findMaxLengthSequence(N, arr) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find longest strictly
// increasing sequence using boundary elements
static void findMaxLengthSequence(int N, int[] arr)
{
// Maintains rightmost element
// in the sequence
int rightmost_element = -1;
// Pointer to start of array
int i = 0;
// Pointer to end of array
int j = N - 1;
// Stores the required sequence
List<int> sequence = new List<int>();
// Traverse the array
while (i <= j) {
// If arr[i]>arr[j]
if (arr[i] > arr[j]) {
// If arr[j] is greater than
// rightmost element of the sequence
if (arr[j] > rightmost_element) {
// Push arr[j] into the sequence
sequence.Add(arr[j]);
// Update rightmost element
rightmost_element = arr[j];
j--;
}
else if (arr[i] > rightmost_element) {
// Push arr[i] into the sequence
sequence.Add(arr[i]);
// Update rightmost element
rightmost_element = arr[i];
i++;
}
else
break;
}
// If arr[i] < arr[j]
else if (arr[i] < arr[j]) {
// If arr[i] > rightmost element
if (arr[i] > rightmost_element) {
// Push arr[i] into the sequence
sequence.Add(arr[i]);
// Update rightmost element
rightmost_element = arr[i];
i++;
}
// If arr[j] > rightmost element
else if (arr[j] > rightmost_element) {
// Push arr[j] into the sequence
sequence.Add(arr[j]);
// Update rightmost element
rightmost_element = arr[j];
j--;
}
else
break;
}
// If arr[i] is equal to arr[j]
else if (arr[i] == arr[j]) {
// If i and j are at the same element
if (i == j) {
// If arr[i] > rightmostelement
if (arr[i] > rightmost_element) {
// Push arr[j] into the sequence
sequence.Add(arr[i]);
// Update rightmost element
rightmost_element = arr[i];
i++;
}
break;
}
else {
sequence.Add(arr[i]);
// Traverse array
// from left to right
int k = i + 1;
// Stores the increasing
// sequence from the left end
List<int> max_left = new List<int>();
// Traverse array from left to right
while (k < j && arr[k] > arr[k - 1])
{
// Push arr[k] to max_left vector
max_left.Add(arr[k]);
k++;
}
// Traverse the array
// from right to left
int l = j - 1;
// Stores the increasing
// sequence from the right end
List<int> max_right = new List<int>();
// Traverse array from right to left
while (l > i && arr[l] > arr[l + 1])
{
// Push arr[k] to max_right vector
max_right.Add(arr[l]);
l--;
}
// If size of max_left is greater
// than max_right
if (max_left.Count > max_right.Count)
foreach(int element in max_left)
// Push max_left elements to
// the original sequence
sequence.Add(element);
// Otherwise
else
foreach(int element in max_right)
// Push max_right elements to
// the original sequence
sequence.Add(element);
break;
}
}
}
// Print the sequence
foreach(int element in sequence)
Console.Write(element + " ");
}
// Driver code
static void Main()
{
int N = 4;
int[] arr = { 1, 3, 2, 1 };
// Print the longest increasing
// sequence using boundary elements
findMaxLengthSequence(N, arr);
}
}
// This code is contribute by divyesh072019
Javascript
<script>
// Javascript program for the above approach
// Function to find longest strictly
// increasing sequence using boundary elements
function findMaxLengthSequence(N, arr)
{
// Maintains rightmost element
// in the sequence
let rightmost_element = -1;
// Pointer to start of array
let i = 0;
// Pointer to end of array
let j = N - 1;
// Stores the required sequence
let sequence = [];
// Traverse the array
while (i <= j)
{
// If arr[i]>arr[j]
if (arr[i] > arr[j])
{
// If arr[j] is greater than
// rightmost element of the sequence
if (arr[j] > rightmost_element)
{
// Push arr[j] into the sequence
sequence.push(arr[j]);
// Update rightmost element
rightmost_element = arr[j];
j--;
}
else if (arr[i] > rightmost_element)
{
// Push arr[i] into the sequence
sequence.push(arr[i]);
// Update rightmost element
rightmost_element = arr[i];
i++;
}
else
break;
}
// If arr[i] < arr[j]
else if (arr[i] < arr[j])
{
// If arr[i] > rightmost element
if (arr[i] > rightmost_element)
{
// Push arr[i] into the sequence
sequence.push(arr[i]);
// Update rightmost element
rightmost_element = arr[i];
i++;
}
// If arr[j] > rightmost element
else if (arr[j] > rightmost_element)
{
// Push arr[j] into the sequence
sequence.push(arr[j]);
// Update rightmost element
rightmost_element = arr[j];
j--;
}
else
break;
}
// If arr[i] is equal to arr[j]
else if (arr[i] == arr[j])
{
// If i and j are at the same element
if (i == j)
{
// If arr[i] > rightmostelement
if (arr[i] > rightmost_element)
{
// Push arr[j] into the sequence
sequence.push(arr[i]);
// Update rightmost element
rightmost_element = arr[i];
i++;
}
break;
}
else
{
sequence.push(arr[i]);
// Traverse array
// from left to right
let k = i + 1;
// Stores the increasing
// sequence from the left end
let max_left = [];
// Traverse array from left to right
while (k < j && arr[k] > arr[k - 1])
{
// Push arr[k] to max_left vector
max_left.push(arr[k]);
k++;
}
// Traverse the array
// from right to left
let l = j - 1;
// Stores the increasing
// sequence from the right end
let max_right = [];
// Traverse array from right to left
while (l > i && arr[l] > arr[l + 1])
{
// Push arr[k] to max_right vector
max_right.push(arr[l]);
l--;
}
// If size of max_left is greater
// than max_right
if (max_left.length > max_right.length)
for(let element = 0;
element < max_left.length;
element++)
// Push max_left elements to
// the original sequence
sequence.push(max_left[element]);
// Otherwise
else
for(let element = 0;
element < max_right.length;
element++)
// Push max_right elements to
// the original sequence
sequence.push(max_right[element]);
break;
}
}
}
// Print the sequence
for(let element = 0;
element < sequence.length;
element++)
document.write(sequence[element] + " ");
}
// Driver code
let N = 4;
let arr = [ 1, 3, 2, 1 ];
// Print the longest increasing
// sequence using boundary elements
findMaxLengthSequence(N, arr);
// This code is contributed by suresh07
</script>
Producción:
1 2 3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)