Dado un arreglo arr de enteros de tamaño N , la tarea es encontrar una subsucesión en la que al invertir el orden se pueda obtener la suma máxima del subarreglo .
Ejemplos:
Entrada : arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}
Salida : [-2 -3 1 5]
Explicación : Después de seleccionar la subsecuencia -2 -3 1 5 y invierta los elementos, la array modificada será {5, 1, 4, -1, -2, -3, -2, -3} y, por lo tanto, la suma máxima contagiosa, es decir, 5 + 1 + 4 = 10Entrada : arr[] = {2, -6, -12, 7, -13, 9, -14}
Salida : [-6 -12 7 9]
Explicación : después de seleccionar la subsecuencia anterior, la array modificada será {2, 9 , 7, -12, -13, -6, -14} y por lo tanto la suma máxima contagiosa es 2 + 9 + 7 = 18
Enfoque: La idea es simple: tenemos que modificar la array de modo que todos los elementos positivos se junten, por lo que tenemos que encontrar la subsecuencia tal que todos los elementos positivos se unan cuando invertimos la subsecuencia.
- Supongamos que hay ” p ” elementos no negativos en el arreglo. Divida la array en dos partes: primero los elementos p y los elementos restantes.
- sean ” px ” elementos no negativos en la primera parte de la array. por lo que los elementos negativos en la primera parte serán:
(tamaño de la primera parte de la array – número de elementos no negativos) = p – p x
- También el número de elementos no negativos en la segunda parte de la array es
(total de elementos no negativos – elementos no negativos en la primera parte de la array) = p – p x
- Así que tenemos que seleccionar elementos negativos p- p x elementos de la primera parte y pp x elementos no negativos de la segunda parte de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
vector<int> findSubsequce(int arr[], int n)
{
int p = 0;
for (int i = 0; i < n; i++) {
if (arr[i] >= 0)
p++;
}
vector<int> res;
// store negative elements present
// from 0 to p-1 index
for (int i = 0; i < p; i++) {
if (arr[i] < 0)
res.push_back(arr[i]);
}
// store non-negative elements
// present from p to n index
for (int i = p; i < n; i++) {
if (arr[i] >= 0)
res.push_back(arr[i]);
}
return res;
}
// Driver code
int main()
{
int arr[] = { -2, -3, 4, -1,
-2, 1, 5, -3 };
int n = sizeof(arr) / sizeof(arr[0]);
vector<int> res = findSubsequce(arr, n);
for (int i = 0; i < res.size(); i++) {
cout << res[i] << " ";
}
}
Java
// Java code to implement the above approach
import java.io.*;
import java.util.*;
class GFG {
public static ArrayList<Integer>
findSubsequence(int arr[], int n)
{
int p = 0;
for (int i = 0; i < n; i++) {
if (arr[i] >= 0)
p++;
}
ArrayList<Integer> res
= new ArrayList<Integer>();
// store negative elements
// present from 0 to p-1 index
for (int i = 0; i < p; i++) {
if (arr[i] < 0)
res.add(arr[i]);
}
// store non-negative elements
// present from p to n index
for (int i = p; i < n; i++) {
if (arr[i] >= 0)
res.add(arr[i]);
}
return res;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { -2, -3, 4, -1, -2, 1, 5, -3 };
int n = arr.length;
ArrayList<Integer> res = findSubsequence(arr, n);
for (int i = 0; i < res.size(); i++) {
System.out.print(res.get(i) + " ");
}
}
}
Python3
# Python 3 code to implement the above approach def findSubsequce(arr, n): p = 0 for i in range(n): if (arr[i] >= 0): p += 1 res = [] # store negative elements present # from 0 to p-1 index for i in range(p): if (arr[i] < 0): res.append(arr[i]) # store non-negative elements # present from p to n index for i in range(p, n): if (arr[i] >= 0): res.append(arr[i]) return res # Driver code if __name__ == "__main__": arr = [-2, -3, 4, -1, -2, 1, 5, -3] n = len(arr) res = findSubsequce(arr, n) for i in range(len(res)): print(res[i], end=" ") # This code is contributed by ukasp.
C#
// C# code to implement the above approach
using System;
using System.Collections;
public class GFG{
public static ArrayList
findSubsequence(int[] arr, int n)
{
int p = 0;
for (int i = 0; i < n; i++) {
if (arr[i] >= 0)
p++;
}
var res = new ArrayList();
// store negative elements
// present from 0 to p-1 index
for (int i = 0; i < p; i++) {
if (arr[i] < 0)
res.Add(arr[i]);
}
// store non-negative elements
// present from p to n index
for (int i = p; i < n; i++) {
if (arr[i] >= 0)
res.Add(arr[i]);
}
return res;
}
// Driver code
static public void Main (){
int[] arr = { -2, -3, 4, -1, -2, 1, 5, -3 };
int n = arr.Length;
ArrayList res = findSubsequence(arr, n);
for (int i = 0; i < res.Count; i++) {
Console.Write(res[i] + " ");
}
}
}
// This code is contributed by hrithikgarg03188.
Javascript
<script>
// JavaScript code for the above approach
function findSubsequce(arr, n)
{
let p = 0;
for (let i = 0; i < n; i++) {
if (arr[i] >= 0)
p++;
}
let res =[];
// store negative elements present
// from 0 to p-1 index
for (let i = 0; i < p; i++) {
if (arr[i] < 0)
res.push(arr[i]);
}
// store non-negative elements
// present from p to n index
for (let i = p; i < n; i++) {
if (arr[i] >= 0)
res.push(arr[i]);
}
return res;
}
// Driver code
let arr = [-2, -3, 4, -1,
-2, 1, 5, -3]
let n = arr.length;
let res = findSubsequce(arr, n);
for (let i = 0; i < res.length; i++) {
document.write(res[i]+ " ")
}
// This code is contributed by Potta Lokesh
</script>
-2 -3 1 5
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array