Una sucesión de números reales positivos S 1 , S 2 , S 3 , …, S N se llama sucesión supercreciente si cada elemento de la sucesión es mayor que la suma de todos los elementos anteriores de la sucesión. Por ejemplo, 1, 3, 6, 13, 27, 52 es tal subsecuencia.
Ahora, dada una secuencia supercreciente S y la suma de una subsecuencia de esta secuencia, la tarea es encontrar la subsecuencia.
Ejemplos:
Entrada: S[] = {17, 25, 46, 94, 201, 400}, suma = 272
Salida: 25 46 201
25 + 46 + 201 = 272
Entrada: S[] = {1, 2, 4, 8, 16}, suma = 12
Salida: 4 8
Planteamiento: Este problema se puede resolver usando la técnica codiciosa . Comenzando desde el último elemento de la array hasta el primer elemento, hay dos casos:
- sum < arr[i]: En este caso, el elemento actual no puede ser parte de la subsecuencia requerida ya que después de incluirlo, la suma de la subsecuencia excederá la suma dada. Así que descarta el elemento actual.
- sum ≥ arr[i]: en este caso, el elemento actual debe incluirse en la subsecuencia requerida. Esto se debe a que si el elemento actual no está incluido, la suma de los elementos anteriores en la array será menor que el elemento actual (ya que es una secuencia supercreciente), que a su vez será menor que la suma requerida. Así que tome el elemento actual y actualice la suma como sum = sum – arr[i] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the required subsequence
void findSubSeq(int arr[], int n, int sum)
{
for (int i = n - 1; i >= 0; i--) {
// Current element cannot be a part
// of the required subsequence
if (sum < arr[i])
arr[i] = -1;
// Include current element in
// the required subsequence
// So update the sum
else
sum -= arr[i];
}
// Print the elements of the
// required subsequence
for (int i = 0; i < n; i++) {
// If the current element was
// included in the subsequence
if (arr[i] != -1)
cout << arr[i] << " ";
}
}
// Driver code
int main()
{
int arr[] = { 17, 25, 46, 94, 201, 400 };
int n = sizeof(arr) / sizeof(int);
int sum = 272;
findSubSeq(arr, n, sum);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to find the required subsequence
static void findSubSeq(int arr[], int n, int sum)
{
for (int i = n - 1; i >= 0; i--)
{
// Current element cannot be a part
// of the required subsequence
if (sum < arr[i])
arr[i] = -1;
// Include current element in
// the required subsequence
// So update the sum
else
sum -= arr[i];
}
// Print the elements of the
// required subsequence
for (int i = 0; i < n; i++)
{
// If the current element was
// included in the subsequence
if (arr[i] != -1)
System.out.print(arr[i] + " ");
}
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 17, 25, 46, 94, 201, 400 };
int n = arr.length;
int sum = 272;
findSubSeq(arr, n, sum);
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function to find the required subsequence def findSubSeq(arr, n, sum) : for i in range(n - 1, -1, -1) : # Current element cannot be a part # of the required subsequence if (sum < arr[i]) : arr[i] = -1; # Include current element in # the required subsequence # So update the sum else : sum -= arr[i]; # Print the elements of the # required subsequence for i in range(n) : # If the current element was # included in the subsequence if (arr[i] != -1) : print(arr[i], end = " "); # Driver code if __name__ == "__main__" : arr = [ 17, 25, 46, 94, 201, 400 ]; n = len(arr); sum = 272; findSubSeq(arr, n, sum); # This code is contributed by kanugargng
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to find the required subsequence
static void findSubSeq(int []arr,
int n, int sum)
{
for (int i = n - 1; i >= 0; i--)
{
// Current element cannot be a part
// of the required subsequence
if (sum < arr[i])
arr[i] = -1;
// Include current element in
// the required subsequence
// So update the sum
else
sum -= arr[i];
}
// Print the elements of the
// required subsequence
for (int i = 0; i < n; i++)
{
// If the current element was
// included in the subsequence
if (arr[i] != -1)
Console.Write(arr[i] + " ");
}
}
// Driver code
public static void Main (String[] args)
{
int []arr = { 17, 25, 46, 94, 201, 400 };
int n = arr.Length;
int sum = 272;
findSubSeq(arr, n, sum);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the approach
// Function to find the required subsequence
function findSubSeq(arr, n, sum) {
for (let i = n - 1; i >= 0; i--) {
// Current element cannot be a part
// of the required subsequence
if (sum < arr[i])
arr[i] = -1;
// Include current element in
// the required subsequence
// So update the sum
else
sum -= arr[i];
}
// Print the elements of the
// required subsequence
for (let i = 0; i < n; i++) {
// If the current element was
// included in the subsequence
if (arr[i] != -1)
document.write(arr[i] + " ");
}
}
// Driver code
let arr = [17, 25, 46, 94, 201, 400];
let n = arr.length;
let sum = 272;
findSubSeq(arr, n, sum);
// This code is contributed by gfgking.
</script>
Producción:
25 46 201
Complejidad de tiempo: O(n)
Publicación traducida automáticamente
Artículo escrito por prateekpratikgupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA