Subsecuencia más larga con suma no negativa

Dada una array arr[] de longitud N , la tarea es encontrar la longitud de la subsecuencia más grande con una suma no negativa.
Ejemplos: 
 

Entrada: arr[] = {1, 2, -3} 
Salida: 3 
La array completa tiene una suma no negativa.
Entrada: arr[] = {1, 2, -4} 
Salida: 2 
{1, 2} es la subsecuencia requerida. 
 

Enfoque: la idea es que todos los números no negativos deben incluirse en la subsecuencia porque dichos números solo aumentarán el valor de la suma total. 
Ahora, no es difícil ver entre números negativos, los más grandes deben elegirse primero. Por lo tanto, siga agregando los números negativos en orden no creciente de sus valores, siempre y cuando no reduzcan el valor de la suma total por debajo de 0. Esto se puede hacer después de ordenar la array.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the length of
// the largest subsequence
// with non-negative sum
int maxLen(int* arr, int n)
{
    // To store the current sum
    int c_sum = 0;
 
    // Sort the input array in
    // non-increasing order
    sort(arr, arr + n, greater<int>());
 
    // Traverse through the array
    for (int i = 0; i < n; i++) {
 
        // Add the current element to the sum
        c_sum += arr[i];
 
        // Condition when c_sum falls
        // below zero
        if (c_sum < 0)
            return i;
    }
 
    // Complete array has a non-negative sum
    return n;
}
 
// Driver code
int main()
{
    int arr[] = { 3, 5, -6 };
    int n = sizeof(arr) / sizeof(int);
 
    cout << maxLen(arr, n);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to return the length of
// the largest subsequence
// with non-negative sum
static int maxLen(int[] arr, int n)
{
    // To store the current sum
    int c_sum = 0;
 
    // Sort the input array in
    // non-increasing order
    Arrays.sort(arr);
 
    // Traverse through the array
    for (int i = n-1; i >=0; i--)
    {
 
        // Add the current element to the sum
        c_sum += arr[i];
 
        // Condition when c_sum falls
        // below zero
        if (c_sum < 0)
            return i;
    }
 
    // Complete array has a non-negative sum
    return n;
}
 
// Driver code
public static void main(String []args)
{
    int arr[] = { 3, 5, -6 };
    int n = arr.length;
 
    System.out.println(maxLen(arr, n));
}
}
 
// This code is contributed by Rajput-Ji

# Python3 implementation of the approach
 
# Function to return the length of
# the largest subsequence
# with non-negative sum
def maxLen(arr, n) :
 
    # To store the current sum
    c_sum = 0;
 
    # Sort the input array in
    # non-increasing order
    arr.sort(reverse = True);
 
    # Traverse through the array
    for i in range(n) :
 
        # Add the current element to the sum
        c_sum += arr[i];
 
        # Condition when c_sum falls
        # below zero
        if (c_sum < 0) :
            return i;
 
    # Complete array has a non-negative sum
    return n;
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 3, 5, -6 ];
    n = len(arr);
 
    print(maxLen(arr, n));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the length of
// the largest subsequence
// with non-negative sum
static int maxLen(int[] arr, int n)
{
    // To store the current sum
    int c_sum = 0;
 
    // Sort the input array in
    // non-increasing order
    Array.Sort(arr);
 
    // Traverse through the array
    for (int i = n - 1; i >= 0; i--)
    {
 
        // Add the current element to the sum
        c_sum += arr[i];
 
        // Condition when c_sum falls
        // below zero
        if (c_sum < 0)
            return i;
    }
 
    // Complete array has a non-negative sum
    return n;
}
 
// Driver code
public static void Main(String []args)
{
    int []arr = { 3, 5, -6 };
    int n = arr.Length;
 
    Console.WriteLine(maxLen(arr, n));
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// Javascript implementation of the approach
 
// Function to return the length of
// the largest subsequence
// with non-negative sum
function maxLen(arr, n)
{
    // To store the current sum
    var c_sum = 0;
 
    // Sort the input array in
    // non-increasing order
    arr.sort((a,b)=> b-a)
 
    // Traverse through the array
    for (var i = 0; i < n; i++) {
 
        // Add the current element to the sum
        c_sum += arr[i];
 
        // Condition when c_sum falls
        // below zero
        if (c_sum < 0)
            return i;
    }
 
    // Complete array has a non-negative sum
    return n;
}
 
// Driver code
var arr = [3, 5, -6];
var n = arr.length;
document.write( maxLen(arr, n));
 
</script>

3

Complejidad de tiempo: O(n*log(n))
Espacio auxiliar: O(1)