Largest sum contiguous subarray having only non-negative elements
Given an integer array arr[], the task is to find the largest sum contiguous subarray of non-negative elements and return its sum.
Examples:
Input: arr[] = {1, 4, -3, 9, 5, -6}
Output: 14
Explanation:
Subarray [9, 5] is the subarray having maximum sum with all non-negative elements.Input: arr[] = {12, 0, 10, 3, 11}
Output: 36
Naive Approach:
The simplest approach is to generate all subarrays having only non-negative elements while traversing the subarray and calculating the sum of every valid subarray and updating the maximum sum.
Time Complexity: O(N^2)
Efficient Approach:
To optimize the above approach, traverse the array, and for every non-negative element encountered, keep calculating the sum. For every negative element encountered, update the maximum sum after comparison with the current sum. Reset the sum to 0 and proceed to the next element.
Below is the implementation of the above approach:
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> |
14
Time Complexity: O(N)
Auxiliary Space: O(1)
Simpler Approach:The idea in this approach is that when each time we add elements, then, the sum should increase. If it doesn’t, then we have encountered a negative value and the sum would be smaller.
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> |
Sub Array : 9 5 Largest Sum : 14
Time Complexity: O(n)
Space complexity: O(1)