Compruebe si existe un subarreglo con una suma mayor que el Array dado

Dada una array de enteros arr , la tarea es verificar si hay una subarreferencia (excepto la array dada) tal que la suma de sus elementos sea mayor o igual que la suma de los elementos de la array dada. Si tal subarreglo no es posible, imprima No , de lo contrario imprima Sí .
Ejemplos: 
 

Entrada: arr = {5, 6, 7, 8} 
Salida: No 
Explicación: 
No hay ningún subarreglo del arreglo dado tal que la suma de sus elementos sea mayor o igual que la suma de los elementos del arreglo dado.
Entrada: arr = {-1, 7, 4} 
Salida: Sí 
Explicación: 
Existe un subarreglo {7, 4} cuya suma es mayor que la suma de los elementos del arreglo dado. 
 

Enfoque: el subarreglo con una suma mayor que la suma del arreglo original solo es posible en una de dos condiciones 
 

• Si la suma de todos los elementos de la array dada es menor o igual a 0
• Si existe un subarreglo de prefijo o sufijo cuya suma es negativa

Entonces, verifique si la suma de todos los subarreglos posibles de prefijos y sufijos es menor o igual a cero, la respuesta es Sí. De lo contrario, la respuesta es No.
A continuación se muestra la implementación del enfoque anterior. 
 

// C++ program to check if a subarray exists
// with sum greater than the given Array
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether there exists
// a subarray whose sum is greater than
// or equal to sum of given array elements
int subarrayPossible(int arr[], int n)
{
    // Initialize sum with 0
    int sum = 0;
 
    // Checking possible prefix subarrays.
    // If sum of them is less than or equal
    // to zero, then return 1
    for (int i = 0; i < n; i++) {
        sum += arr[i];
 
        if (sum <= 0)
            return 1;
    }
 
    // again reset sum to zero
    sum = 0;
 
    // Checking possible suffix subarrays.
    // If sum of them is less than or equal
    // to zero, then return 1
    for (int i = n - 1; i >= 0; i--) {
        sum += arr[i];
 
        if (sum <= 0)
            return 1;
    }
 
    // Otherwise return 0
    return 0;
}
 
// Driver Code
int main()
{
    int arr[] = { 10, 5, -12, 7, -10, 20,
                  30, -10, 50, 60 };
 
    int size = sizeof(arr) / sizeof(arr[0]);
 
    if (subarrayPossible(arr, size))
        cout << "Yes"
             << "\n";
    else
        cout << "No"
             << "\n";
 
    return 0;
}

// Java program to check if a subarray exists
// with sum greater than the given Array
import java.util.*;
 
class GFG{
 
    // Function to check whether there exists
    // a subarray whose sum is greater than
   // or equal to sum of given array elements
    static boolean subarrayPossible(int arr[], int n)
    {
        // Initialize sum with 0
        int sum = 0;
     
        // Checking possible prefix subarrays.
        // If sum of them is less than or equal
        // to zero, then return 1
        for (int i = 0; i < n; i++) {
            sum += arr[i];
     
            if (sum <= 0)
                return true;
        }
     
        // again reset sum to zero
        sum = 0;
     
        // Checking possible suffix subarrays.
        // If sum of them is less than or equal
        // to zero, then return 1
        for (int i = n - 1; i >= 0; i--) {
            sum += arr[i];
     
            if (sum <= 0)
                return true;
        }
     
        // Otherwise return 0
        return false;
    }
     
    // Driver Code
    public static void main(String args[])
    {
        int arr[] = { 10, 5, -12, 7, -10, 20, 30, -10, 50, 60 };
     
        int size = arr.length;
     
        if (subarrayPossible(arr, size))
            System.out.print("Yes"+"\n");
        else
            System.out.print("No"+"\n");
    }
}
 
// This code is contributed by AbhiThakur

# Python3 program to check if a subarray exists
# with sum greater than the given Array
 
# Function to check whether there exists
# a subarray whose sum is greater than
# or equal to sum of given array elements
def subarrayPossible(arr, n):
    # Initialize sum with 0
    sum = 0;
 
    # Checking possible prefix subarrays.
    # If sum of them is less than or equal
    # to zero, then return 1
    for i in range(n):
        sum += arr[i];
 
        if (sum <= 0):
            return True;
     
 
    # again reset sum to zero
    sum = 0;
 
    # Checking possible suffix subarrays.
    # If sum of them is less than or equal
    # to zero, then return 1
    for i in range(n-1, -1,-1):
        sum += arr[i];
 
        if (sum <= 0):
            return True;
     
 
    # Otherwise return 0
    return False;
 
# Driver Code
if __name__ == '__main__':
    arr = [ 10, 5, -12, 7, -10, 20, 30, -10, 50, 60 ];
 
    size = len(arr);
 
    if (subarrayPossible(arr, size)):
        print("Yes");
    else:
        print("No");
 
# This code is contributed by Princi Singh

// C# program to check if a subarray exists
// with sum greater than the given Array
using System;
 
class GFG{
  
// Function to check whether there exists
// a subarray whose sum is greater than
// or equal to sum of given array elements
    static bool subarrayPossible(int []arr, int n)
    {
        // Initialize sum with 0
        int sum = 0;
      
        // Checking possible prefix subarrays.
        // If sum of them is less than or equal
        // to zero, then return 1
        for (int i = 0; i < n; i++) {
            sum += arr[i];
      
            if (sum <= 0)
                return true;
        }
      
        // again reset sum to zero
        sum = 0;
      
        // Checking possible suffix subarrays.
        // If sum of them is less than or equal
        // to zero, then return 1
        for (int i = n - 1; i >= 0; i--) {
            sum += arr[i];
      
            if (sum <= 0)
                return true;
        }
      
        // Otherwise return 0
        return false;
    }
      
    // Driver Code
    public static void Main(String []args)
    {
        int []arr = { 10, 5, -12, 7, -10, 20, 30, -10, 50, 60 };
      
        int size = arr.Length;
      
        if (subarrayPossible(arr, size))
            Console.Write("Yes"+"\n");
        else
            Console.Write("No"+"\n");
    }
}
 
// This code is contributed by Princi Singh

<script>
 
// JavaScript program to check if a subarray exists
// with sum greater than the given Array
 
    // Function to check whether there exists
    // a subarray whose sum is greater than
   // or equal to sum of given array elements
    function subarrayPossible(arr, n)
    {
        // Initialize sum with 0
        let sum = 0;
       
        // Checking possible prefix subarrays.
        // If sum of them is less than or equal
        // to zero, then return 1
        for (let i = 0; i < n; i++) {
            sum += arr[i];
       
            if (sum <= 0)
                return true;
        }
       
        // again reset sum to zero
        sum = 0;
       
        // Checking possible suffix subarrays.
        // If sum of them is less than or equal
        // to zero, then return 1
        for (let i = n - 1; i >= 0; i--) {
            sum += arr[i];
       
            if (sum <= 0)
                return true;
        }
       
        // Otherwise return 0
        return false;
    }
 
// Driver Code
 
    let arr = [ 10, 5, -12, 7, -10, 20, 30, -10, 50, 60 ];
       
        let size = arr.length;
       
        if (subarrayPossible(arr, size))
            document.write("Yes"+"<br/>");
        else
           document.write("No"+"<br/>");
 
</script>

Yes

Análisis de rendimiento : 
 

• Complejidad de tiempo : en el enfoque anterior, estamos iterando sobre la array de longitud N dos veces, por lo que la complejidad de tiempo es O(N) . 
   
• Complejidad del espacio auxiliar : en el enfoque anterior, estamos usando solo unas pocas constantes, por lo que la complejidad del espacio auxiliar es O(1) .