Dado un arreglo entero arr[] , la tarea es encontrar el subarreglo contiguo de suma más grande de elementos no negativos y devolver su suma.
Ejemplos:
Entrada: array[] = {1, 4, -3, 9, 5, -6}
Salida: 14
Explicación:
el subarreglo [9, 5] es el subarreglo que tiene la suma máxima con todos los elementos no negativos.Entrada: arr[] = {12, 0, 10, 3, 11}
Salida: 36
Enfoque ingenuo:
el enfoque más simple es generar todos los subarreglos que tienen solo elementos no negativos mientras se recorre el subarreglo y se calcula la suma de cada subarreglo válido y se actualiza la suma máxima.
Complejidad del tiempo: O(N^2)
Enfoque eficiente:
para optimizar el enfoque anterior, recorra la array y, para cada elemento no negativo encontrado, siga calculando la suma. Para cada elemento negativo encontrado, actualice la suma máxima después de la comparación con la suma actual. Restablezca la suma a 0 y continúe con el siguiente elemento.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return Largest Sum Contiguous
// Subarray having non-negative number
int maxNonNegativeSubArray(int A[], int N)
{
// Length of given array
int l = N;
int sum = 0, i = 0;
int Max = -1;
// Traversing array
while (i < l)
{
// Increment i counter to avoid
// negative elements
while (i < l && A[i] < 0)
{
i++;
continue;
}
// Calculating sum of contiguous
// subarray of non-negative
// elements
while (i < l && 0 <= A[i])
{
sum += A[i++];
// Update the maximum sum
Max = max(Max, sum);
}
// Reset sum
sum = 0;
}
// Return the maximum sum
return Max;
}
// Driver code
int main()
{
int arr[] = { 1, 4, -3, 9, 5, -6 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << maxNonNegativeSubArray(arr, N);
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG {
// Function to return Largest Sum Contiguous
// Subarray having non-negative number
static int maxNonNegativeSubArray(int[] A)
{
// Length of given array
int l = A.length;
int sum = 0, i = 0;
int max = -1;
// Traversing array
while (i < l) {
// Increment i counter to avoid
// negative elements
while (i < l && A[i] < 0) {
i++;
continue;
}
// Calculating sum of contiguous
// subarray of non-negative
// elements
while (i < l && 0 <= A[i]) {
sum += A[i++];
// Update the maximum sum
max = Math.max(max, sum);
}
// Reset sum
sum = 0;
}
// Return the maximum sum
return max;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 4, -3, 9, 5, -6 };
System.out.println(maxNonNegativeSubArray(
arr));
}
}
Python3
# Python3 program for the above approach import math # Function to return Largest Sum Contiguous # Subarray having non-negative number def maxNonNegativeSubArray(A, N): # Length of given array l = N sum = 0 i = 0 Max = -1 # Traversing array while (i < l): # Increment i counter to avoid # negative elements while (i < l and A[i] < 0): i += 1 continue # Calculating sum of contiguous # subarray of non-negative # elements while (i < l and 0 <= A[i]): sum += A[i] i += 1 # Update the maximum sum Max = max(Max, sum) # Reset sum sum = 0; # Return the maximum sum return Max # Driver code arr = [ 1, 4, -3, 9, 5, -6 ] # Length of array N = len(arr) print(maxNonNegativeSubArray(arr, N)) # This code is contributed by sanjoy_62
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to return Largest Sum Contiguous
// Subarray having non-negative number
static int maxNonNegativeSubArray(int[] A)
{
// Length of given array
int l = A.Length;
int sum = 0, i = 0;
int max = -1;
// Traversing array
while (i < l)
{
// Increment i counter to avoid
// negative elements
while (i < l && A[i] < 0)
{
i++;
continue;
}
// Calculating sum of contiguous
// subarray of non-negative
// elements
while (i < l && 0 <= A[i])
{
sum += A[i++];
// Update the maximum sum
max = Math.Max(max, sum);
}
// Reset sum
sum = 0;
}
// Return the maximum sum
return max;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 4, -3, 9, 5, -6 };
Console.Write(maxNonNegativeSubArray(arr));
}
}
// This code is contributed by chitranayal
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to return Largest Sum Contiguous
// Subarray having non-negative number
function maxNonNegativeSubArray(A, N)
{
// Length of given array
var l = N;
var sum = 0, i = 0;
var Max = -1;
// Traversing array
while (i < l)
{
// Increment i counter to avoid
// negative elements
while (i < l && A[i] < 0)
{
i++;
continue;
}
// Calculating sum of contiguous
// subarray of non-negative
// elements
while (i < l && 0 <= A[i])
{
sum += A[i++];
// Update the maximum sum
Max = Math.max(Max, sum);
}
// Reset sum
sum = 0;
}
// Return the maximum sum
return Max;
}
// Driver code
var arr = [1, 4, -3, 9, 5, -6];
var N = arr.length;
document.write( maxNonNegativeSubArray(arr, N));
// This code is contributed by famously.
</script>
Producción
14
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
Enfoque más simple: la idea de este enfoque es que cada vez que agregamos elementos, la suma debe aumentar. Si no es así, entonces hemos encontrado un valor negativo y la suma sería menor.
C++
#include <iostream>
using namespace std;
int main()
{
int arr[] = { 1, 4, -3, 9, 5, -6 };
int n = sizeof(arr) / sizeof(arr[0]);
int max_so_far = 0, max_right_here = 0;
int start = 0, end = 0, s = 0;
for (int i = 0; i < n; i++) {
if (arr[i] < 0) {
s = i + 1;
max_right_here = 0;
}
else {
max_right_here += arr[i];
}
if (max_right_here > max_so_far) {
max_so_far = max_right_here;
start = s;
end = i;
}
}
cout << ("Sub Array : ");
for (int i = start; i <= end; i++) {
cout << arr[i] << " ";
}
cout << endl;
cout << "Largest Sum : " << max_so_far;
}
// This code is contributed by SoumikMondal
Java
import java.util.*;
class GFG
{
public static void main(String[] args)
{
int arr[] = { 1, 4, -3, 9, 5, -6 };
int n = arr.length;
int max_so_far = 0, max_right_here = 0;
int start = 0, end = 0, s = 0;
for (int i = 0; i < n; i++) {
if (arr[i] < 0) {
s = i + 1;
max_right_here = 0;
}
else {
max_right_here += arr[i];
}
if (max_right_here > max_so_far) {
max_so_far = max_right_here;
start = s;
end = i;
}
}
System.out.print("Sub Array : ");
for (int i = start; i <= end; i++) {
System.out.print( arr[i]);
System.out.print(" ");
}
System.out.println();
System.out.print("Largest Sum : ");
System.out.print( max_so_far);
}
}
// This code is contributed by amreshkumar3.
Python3
arr = [1, 4, -3, 9, 5, -6]
n = len(arr)
max_so_far = 0
max_right_here = 0
start = 0
end = 0
s = 0
for i in range(0, n):
if arr[i] < 0:
s = i + 1
max_right_here = 0
else:
max_right_here += arr[i]
if max_right_here > max_so_far:
max_so_far = max_right_here
start = s
end = i
print("Sub Array : ")
for i in range(start, end + 1):
print(arr[i], end=" ")
print()
print("largest sum=", max_so_far)
# This code is contributed by amreshkumar3.
C#
using System;
public class GFG {
public static void Main(String[] args)
{
int[] arr = { 1, 4, -3, 9, 5, -6 };
int n = arr.Length;
int max_so_far = 0, max_right_here = 0;
int start = 0, end = 0, s = 0;
for (int i = 0; i < n; i++) {
if (arr[i] < 0) {
s = i + 1;
max_right_here = 0;
}
else {
max_right_here += arr[i];
}
if (max_right_here > max_so_far) {
max_so_far = max_right_here;
start = s;
end = i;
}
}
Console.Write("Sub Array : ");
for (int i = start; i <= end; i++) {
Console.Write(arr[i]);
Console.Write(" ");
}
Console.WriteLine();
Console.Write("Largest Sum : ");
Console.Write(max_so_far);
}
}
// This code is contributed by umadevi9616
Javascript
<script>
let arr = [ 1, 4, -3, 9, 5, -6 ];
let n = arr.length;
let max_so_far = 0, max_right_here = 0;
let start = 0, end = 0, s = 0;
for(let i = 0; i < n; i++)
{
if (arr[i] < 0)
{
s = i + 1;
max_right_here = 0;
}
else
{
max_right_here += arr[i];
}
if (max_right_here > max_so_far)
{
max_so_far = max_right_here;
start = s;
end = i;
}
}
// Driver code
document.write("Sub Array : ");
for(let i = start; i <= end; i++)
{
document.write(arr[i] + " ");
}
document.write("<br>");
document.write("Largest Sum : " + max_so_far);
// This code is contributed by Potta Lokesh
</script>
Producción
Sub Array : 9 5 Largest Sum : 14
Complejidad de tiempo: O(n)
Complejidad del espacio: O(1)