Dada una array de N enteros. La tarea es encontrar el subarreglo de longitud máxima tal que la suma de todos sus elementos sea mayor o igual a 0.
Ejemplos :
Input: arr[]= {-1, 4, -2, -5, 6, -8}
Output: 5
Explanation: {-1, 4, -2, -5, 6} forms the longest subarray with sum=2.
Input: arr[]={-5, -6}
Output: 0
Explanation: No such subarray is possible
Un enfoque ingenuo es precalcular la suma del prefijo de la array. Luego use dos bucles anidados para cada índice inicial y final y si la suma del prefijo hasta el índice final es menos la suma del prefijo antes del índice inicial es mayor que igual a 0, actualice la respuesta en consecuencia.
Tiempo Complejidad : O(N 2 )
Un enfoque eficiente es utilizar la búsqueda binaria para resolver el siguiente problema. A continuación se muestran los pasos para resolver el problema anterior:
- Primero, calcule la suma del sufijo para cada índice de la array y guárdela en otra array.
- Utilice otro espacio de búsqueda de arrays para almacenar los puntos de inicio de cada subarreglo.
- Iterar desde el índice 0 y si el sufijo hasta ese índice i es mayor que el elemento superior en el espacio de búsqueda, agregue esa suma de sufijo al espacio de búsqueda.
- Use la búsqueda binaria para encontrar el índice más bajo en el espacio de búsqueda de modo que la suma del sufijo hasta ese índice menos la suma del sufijo hasta (i+1)’th sea mayor que igual a 0. Si existe algún índice de este tipo, actualice la respuesta en consecuencia .
La observación clave aquí es que agregue una suma de sufijos al espacio de búsqueda si es mayor que todas las demás sumas de sufijos en el espacio de búsqueda, ya que la longitud debe maximizarse.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ Program to compute the
// longest subarray with
// sum greater than equal to 0.
#include <bits/stdc++.h>
using namespace std;
// Function for the searching the
// starting index of the subarray
int search(int* searchspace, int s, int e, int key)
{
// -1 signifies that no
// starting point of the subarray
// is not found with sum greater
// than equal to 0.
int ans = -1;
// Binary search
while (s <= e) {
int mid = (s + e) / 2;
if (searchspace[mid] - key >= 0) {
ans = mid;
e = mid - 1;
}
else {
s = mid + 1;
}
}
return ans;
}
// Function to return the longest subarray
int longestSubarray(int a[], int n)
{
// Array for the suffix sum
// of the above the array.
int SuffixSum[n + 1];
SuffixSum[n] = 0;
for (int i = n - 1; i >= 0; --i) {
SuffixSum[i] = SuffixSum[i + 1] + a[i];
}
int ans = 0;
// Search Space for potential starting
// points of the subarray.
// It will store the suffix sum
// till i'th index in increasing order.
int searchspace[n];
// It will store the indexes
// till which the suffix sum
// is present in search space.
int index[n];
int j = 0;
for (int i = 0; i < n; ++i) {
// add the element to the search space if the j=0
// or if the topmost element is lesser
// than present suffix sum.
if (j == 0 or SuffixSum[i] > searchspace[j - 1]) {
searchspace[j] = SuffixSum[i];
index[j] = i;
j++;
}
int idx = search(searchspace, 0, j - 1, SuffixSum[i + 1]);
// Only when idx is not -1 an subarray is
// possible with ending index at i.
if (idx != -1)
ans = max(ans, i - index[idx] + 1);
}
return ans;
}
// Driver Code
int main()
{
int a[] = { -1, 4, -2, -5, 6, -8 };
int n = sizeof(a) / sizeof(a[0]);
cout << longestSubarray(a, n);
return 0;
}
Java
// Java Program to compute the
// longest subarray with
// sum greater than equal to 0.
import java.io.*;
class GFG {
// Function for the searching the
// starting index of the subarray
static int search(int searchspace[], int s, int e, int key)
{
// -1 signifies that no
// starting point of the subarray
// is not found with sum greater
// than equal to 0.
int ans = -1;
// Binary search
while (s <= e) {
int mid = (s + e) / 2;
if (searchspace[mid] - key >= 0) {
ans = mid;
e = mid - 1;
}
else {
s = mid + 1;
}
}
return ans;
}
// Function to return the longest subarray
static int longestSubarray(int []a, int n)
{
// Array for the suffix sum
// of the above the array.
int SuffixSum[] = new int[n+1];
SuffixSum[n] = 0;
for (int i = n - 1; i >= 0; --i) {
SuffixSum[i] = SuffixSum[i + 1] + a[i];
}
int ans = 0;
// Search Space for potential starting
// points of the subarray.
// It will store the suffix sum
// till i'th index in increasing order.
int searchspace[] = new int[n];
// It will store the indexes
// till which the suffix sum
// is present in search space.
int index[] = new int[n];
int j = 0;
for (int i = 0; i < n; ++i) {
// add the element to the search space if the j=0
// or if the topmost element is lesser
// than present suffix sum.
if ((j == 0) || SuffixSum[i] > searchspace[j - 1]) {
searchspace[j] = SuffixSum[i];
index[j] = i;
j++;
}
int idx = search(searchspace, 0, j - 1, SuffixSum[i + 1]);
// Only when idx is not -1 an subarray is
// possible with ending index at i.
if (idx != -1)
ans = Math.max(ans, i - index[idx] + 1);
}
return ans;
}
// Driver Code
public static void main (String[] args) {
int []a = { -1, 4, -2, -5, 6, -8 };
int n = a.length;
System.out.println(longestSubarray(a, n));
}
}
// This code is contributed
// by anuj_67..
Python3
# Python3 program to compute the longest # with sum greater than equal to 0 import math as mt # function for the searching the # starting index of the subarray def search(searchspace, s, e, key): # -1 signifies that no starting point # of the subarray is not found with # sum greater than equal to 0. ans = -1 # Binary search while s <= e: mid = (s + e) // 2 if searchspace[mid] - key >= 0: ans = mid e = mid - 1 else: s = mid + 1 return ans # function to return the longest subarray def longestSubarray(a, n): # Array for the suffix sum of # the above the array SuffixSum = [0 for i in range(n + 1)] for i in range(n - 1, -1, -1): SuffixSum[i] = SuffixSum[i + 1] + a[i] ans = 0 # Search Space for potential starting # points of the subarray. # It will store the suffix sum # till i'th index in increasing order searchspace = [0 for i in range(n)] # It will store the indexes # till which the suffix sum # is present in search space index = [0 for i in range(n)] j = 0 for i in range(n): # add the element to the search space # if the j=0 or if the topmost element # is lesser than present suffix sum if j == 0 or (SuffixSum[i] > searchspace[j - 1]): searchspace[j] = SuffixSum[i] index[j] = i j += 1 idx = search(searchspace, 0, j - 1, SuffixSum[i + 1]) # Only when idx is not -1 an subarray is # possible with ending index at i. if idx != -1: ans = max(ans, i - index[idx] + 1) return ans # Driver Code a = [-1, 4, -2, -5, 6, -8] n = len(a) print(longestSubarray(a, n)) # This code is contributed # by Mohit kumar 29
C#
// C# Program to compute the
// longest subarray with
// sum greater than equal to 0.
using System;
class GFG {
// Function for the searching the
// starting index of the subarray
static int search(int[] searchspace, int s, int e, int key)
{
// -1 signifies that no
// starting point of the subarray
// is not found with sum greater
// than equal to 0.
int ans = -1;
// Binary search
while (s <= e) {
int mid = (s + e) / 2;
if (searchspace[mid] - key >= 0) {
ans = mid;
e = mid - 1;
}
else {
s = mid + 1;
}
}
return ans;
}
// Function to return the longest subarray
static int longestSubarray(int[] a, int n)
{
// Array for the suffix sum
// of the above the array.
int[] SuffixSum = new int[n+1];
SuffixSum[n] = 0;
for (int i = n - 1; i >= 0; --i) {
SuffixSum[i] = SuffixSum[i + 1] + a[i];
}
int ans = 0;
// Search Space for potential starting
// points of the subarray.
// It will store the suffix sum
// till i'th index in increasing order.
int[] searchspace = new int[n];
// It will store the indexes
// till which the suffix sum
// is present in search space.
int[] index = new int[n];
int j = 0;
for (int i = 0; i < n; ++i) {
// add the element to the search space if the j=0
// or if the topmost element is lesser
// than present suffix sum.
if ((j == 0) || SuffixSum[i] > searchspace[j - 1]) {
searchspace[j] = SuffixSum[i];
index[j] = i;
j++;
}
int idx = search(searchspace, 0, j - 1, SuffixSum[i + 1]);
// Only when idx is not -1 an subarray is
// possible with ending index at i.
if (idx != -1)
ans = Math.Max(ans, i - index[idx] + 1);
}
return ans;
}
// Driver Code
public static void Main () {
int[] a = { -1, 4, -2, -5, 6, -8 };
int n = a.Length;
Console.Write(longestSubarray(a, n));
}
}
PHP
<?php
// PHP Program to compute the
// longest subarray with
// sum greater than equal to 0.
// Function for the searching the
// starting index of the subarray
function search($searchspace, $s,
$e, $key)
{
// -1 signifies that no starting
// point of the subarray is not
// found with sum greater than
// equal to 0.
$ans = -1;
// Binary search
while ($s <= $e)
{
$mid = ($s + $e) / 2;
if ($searchspace[$mid] - $key >= 0)
{
$ans = $mid;
$e = $mid - 1;
}
else
{
$s = $mid + 1;
}
}
return $ans;
}
// Function to return the
// longest subarray
function longestSubarray(&$a, $n)
{
// Array for the suffix sum
// of the above the array.
$SuffixSum[$n] = 0;
for ($i = $n - 1; $i >= 0; --$i)
{
$SuffixSum[$i] = $SuffixSum[$i + 1] +
$a[$i];
}
$ans = 0;
// Search Space for potential
// starting points of the subarray.
// It will store the suffix sum
// till i'th index in increasing order.
// It will store the indexes
// till which the suffix sum
// is present in search space.
$j = 0;
for ($i = 0; $i < $n; ++$i)
{
// add the element to the search
// space if the j=0 or if the
// topmost element is lesser
// than present suffix sum.
if ($j == 0 or $SuffixSum[$i] >
$searchspace[$j - 1])
{
$searchspace[$j] = $SuffixSum[$i];
$index[$j] = $i;
$j++;
}
$idx = search($searchspace, 0, $j - 1,
$SuffixSum[$i + 1]);
// Only when idx is not -1 an
// subarray is possible with
// ending index at i.
if ($idx != -1)
$ans = max($ans, $i -
$index[$idx] + 1);
}
return $ans;
}
// Driver Code
$a = array(-1, 4, -2, -5, 6, -8 );
$n = sizeof($a);
echo (longestSubarray($a, $n));
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// Javascript Program to compute the
// longest subarray with
// sum greater than equal to 0.
// Function for the searching the
// starting index of the subarray
function search(searchspace,s,e,key)
{
// -1 signifies that no
// starting point of the subarray
// is not found with sum greater
// than equal to 0.
let ans = -1;
// Binary search
while (s <= e) {
let mid = Math.floor((s + e) / 2);
if (searchspace[mid] - key >= 0) {
ans = mid;
e = mid - 1;
}
else {
s = mid + 1;
}
}
return ans;
}
// Function to return the longest subarray
function longestSubarray(a,n)
{
// Array for the suffix sum
// of the above the array.
let SuffixSum = new Array(n+1);
SuffixSum[n] = 0;
for (let i = n - 1; i >= 0; --i) {
SuffixSum[i] = SuffixSum[i + 1] + a[i];
}
let ans = 0;
// Search Space for potential starting
// points of the subarray.
// It will store the suffix sum
// till i'th index in increasing order.
let searchspace = new Array(n);
// It will store the indexes
// till which the suffix sum
// is present in search space.
let index = new Array(n);
let j = 0;
for (let i = 0; i < n; ++i) {
// add the element to the search space if the j=0
// or if the topmost element is lesser
// than present suffix sum.
if ((j == 0) || SuffixSum[i] > searchspace[j - 1]) {
searchspace[j] = SuffixSum[i];
index[j] = i;
j++;
}
let idx = search(searchspace, 0, j - 1, SuffixSum[i + 1]);
// Only when idx is not -1 an subarray is
// possible with ending index at i.
if (idx != -1)
ans = Math.max(ans, i - index[idx] + 1);
}
return ans;
}
// Driver Code
let a=[-1, 4, -2, -5, 6, -8];
let n = a.length;
document.write(longestSubarray(a, n));
// This code is contributed by rag2127
</script>
Producción:
5
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por imdhruvgupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA