Print the Maximum Subarray Sum
Given an array arr[], the task is to find the elements of a contiguous subarray of numbers that has the largest sum.
Examples:
Input: arr = [-2, -3, 4, -1, -2, 1, 5, -3]
Output: [4, -1, -2, 1, 5]
Explanation:
In the above input the maximum contiguous subarray sum is 7 and the elements of the subarray are [4, -1, -2, 1, 5]Input: arr = [-2, -5, 6, -2, -3, 1, 5, -6]
Output: [6, -2, -3, 1, 5]
Explanation:
In the above input the maximum contiguous subarray sum is 7 and the elements
of the subarray are [6, -2, -3, 1, 5]
Naive Approach: The naive approach is to generate all the possible subarray and print that subarray which has maximum sum.
Time complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The idea is to use the Kadane’s Algorithm to find the maximum subarray sum and store the starting and ending index of the subarray having maximum sum and print the subarray from starting index to ending index. Below are the steps:
- Initialize 3 variables endIndex to 0, currMax, and globalMax to first value of the input array.
- For each element in the array starting from index(say i) 1, update currMax to max(nums[i], nums[i] + currMax) and globalMax and endIndex to i only if currMax > globalMax.
- To find the start index, iterate from endIndex in the left direction and keep decrementing the value of globalMax until it becomes 0. The point at which it becomes 0 is the start index.
- Now print the subarray between [start, end].
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to print the elements // of Subarray with maximum sum void SubarrayWithMaxSum(vector< int >& nums) { // Initialize currMax and globalMax // with first value of nums int endIndex, currMax = nums[0]; int globalMax = nums[0]; // Iterate for all the elements // of the array for ( int i = 1; i < nums.size(); ++i) { // Update currMax currMax = max(nums[i], nums[i] + currMax); // Check if currMax is greater // than globalMax if (currMax > globalMax) { globalMax = currMax; endIndex = i; } } int startIndex = endIndex; // Traverse in left direction to // find start Index of subarray while (startIndex >= 0) { globalMax -= nums[startIndex]; if (globalMax == 0) break ; // Decrement the start index startIndex--; } // Printing the elements of // subarray with max sum for ( int i = startIndex; i <= endIndex; ++i) { cout << nums[i] << " " ; } } // Driver Code int main() { // Given array arr[] vector< int > arr = { -2, -5, 6, -2, -3, 1, 5, -6 }; // Function call SubarrayWithMaxSum(arr); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to print the elements // of Subarray with maximum sum static void SubarrayWithMaxSum(Vector<Integer> nums) { // Initialize currMax and globalMax // with first value of nums int endIndex = 0 , currMax = nums.get( 0 ); int globalMax = nums.get( 0 ); // Iterate for all the elements // of the array for ( int i = 1 ; i < nums.size(); ++i) { // Update currMax currMax = Math.max(nums.get(i), nums.get(i) + currMax); // Check if currMax is greater // than globalMax if (currMax > globalMax) { globalMax = currMax; endIndex = i; } } int startIndex = endIndex; // Traverse in left direction to // find start Index of subarray while (startIndex >= 0 ) { globalMax -= nums.get(startIndex); if (globalMax == 0 ) break ; // Decrement the start index startIndex--; } // Printing the elements of // subarray with max sum for ( int i = startIndex; i <= endIndex; ++i) { System.out.print(nums.get(i) + " " ); } } // Driver Code public static void main(String[] args) { // Given array arr[] Vector<Integer> arr = new Vector<Integer>(); arr.add(- 2 ); arr.add(- 5 ); arr.add( 6 ); arr.add(- 2 ); arr.add(- 3 ); arr.add( 1 ); arr.add( 5 ); arr.add(- 6 ); // Function call SubarrayWithMaxSum(arr); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approach # Function to print the elements # of Subarray with maximum sum def SubarrayWithMaxSum(nums): # Initialize currMax and globalMax # with first value of nums currMax = nums[ 0 ] globalMax = nums[ 0 ] # Iterate for all the elements # of the array for i in range ( 1 , len (nums)): # Update currMax currMax = max (nums[i], nums[i] + currMax) # Check if currMax is greater # than globalMax if (currMax > globalMax): globalMax = currMax endIndex = i startIndex = endIndex # Traverse in left direction to # find start Index of subarray while (startIndex > = 0 ): globalMax - = nums[startIndex] if (globalMax = = 0 ): break # Decrement the start index startIndex - = 1 # Printing the elements of # subarray with max sum for i in range (startIndex, endIndex + 1 ): print (nums[i], end = " " ) # Driver Code # Given array arr[] arr = [ - 2 , - 5 , 6 , - 2 , - 3 , 1 , 5 , - 6 ] # Function call SubarrayWithMaxSum(arr) # This code is contributed by sanjoy_62 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to print the elements // of Subarray with maximum sum static void SubarrayWithMaxSum(List< int > nums) { // Initialize currMax and globalMax // with first value of nums int endIndex = 0, currMax = nums[0]; int globalMax = nums[0]; // Iterate for all the elements // of the array for ( int i = 1; i < nums.Count; ++i) { // Update currMax currMax = Math.Max(nums[i], nums[i] + currMax); // Check if currMax is greater // than globalMax if (currMax > globalMax) { globalMax = currMax; endIndex = i; } } int startIndex = endIndex; // Traverse in left direction to // find start Index of subarray while (startIndex >= 0) { globalMax -= nums[startIndex]; if (globalMax == 0) break ; // Decrement the start index startIndex--; } // Printing the elements of // subarray with max sum for ( int i = startIndex; i <= endIndex; ++i) { Console.Write(nums[i] + " " ); } } // Driver Code public static void Main(String[] args) { // Given array []arr List< int > arr = new List< int >(); arr.Add(-2); arr.Add(-5); arr.Add(6); arr.Add(-2); arr.Add(-3); arr.Add(1); arr.Add(5); arr.Add(-6); // Function call SubarrayWithMaxSum(arr); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // Javascript program for the above approach // Function to print the elements // of Subarray with maximum sum function SubarrayWithMaxSum(nums) { // Initialize currMax and globalMax // with first value of nums var endIndex, currMax = nums[0]; var globalMax = nums[0]; // Iterate for all the elements // of the array for ( var i = 1; i < nums.length; ++i) { // Update currMax currMax = Math.max(nums[i], nums[i] + currMax); // Check if currMax is greater // than globalMax if (currMax > globalMax) { globalMax = currMax; endIndex = i; } } var startIndex = endIndex; // Traverse in left direction to // find start Index of subarray while (startIndex >= 0) { globalMax -= nums[startIndex]; if (globalMax == 0) break ; // Decrement the start index startIndex--; } // Printing the elements of // subarray with max sum for ( var i = startIndex; i <= endIndex; ++i) { document.write(nums[i] + " " ); } } // Driver Code // Given array arr[] var arr = [ -2, -5, 6, -2, -3, 1, 5, -6 ]; // Function call SubarrayWithMaxSum(arr); // This code is contributed by rutvik_56 </script> |
6 -2 -3 1 5
Time complexity: O(N)
Auxiliary Space: O(1)
Alternate Efficient Approach: This approach eliminates the inner while loop that moves in left direction decrementing global_max in the above-mentioned method. Thus this method reduces the time.
- Initialize currMax and globalMax to first value of the input array. Initialize endIndex, startIndex, globalMaxStartIndex to 0. ( endIndex, startIndex store the start and end indices of the max sum sub-array ending at i. globalMaxStartIndex stores the startIndex of the globalMax )
- For each element in the array starting from index (say i) 1, update currMax and startIndex to i if nums[i] > nums[i] + currMax. Else only update currMax.
- Update globalMax if currMax>globalMax. Also update globalMaxStartIndex.
- Now print the subarray between [start index, globalMaxStartIndex].
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> #include <vector> using namespace std; // Function to print the elements // of Subarray with maximum sum void SubarrayWithMaxSum(vector< int > nums) { // Initialize currMax and globalMax // with first value of nums int currMax = nums[0], globalMax = nums[0]; // Initialize endIndex startIndex,globalStartIndex int endIndex = 0; int startIndex = 0, globalMaxStartIndex = 0; // Iterate for all the elements of the array for ( int i = 1; i < nums.size(); ++i) { // Update currMax and startIndex if (nums[i] > nums[i] + currMax) { currMax = nums[i]; startIndex = i; // update the new startIndex } // Update currMax else if (nums[i] < nums[i] + currMax) { currMax = nums[i] + currMax; } // Update globalMax and globalMaxStartIndex if (currMax > globalMax) { globalMax = currMax; endIndex = i; globalMaxStartIndex = startIndex; } } // Printing the elements of subarray with max sum for ( int i = globalMaxStartIndex; i <= endIndex; ++i) { cout << nums[i] << " " ; } } // Driver Code int main() { // Given array arr[] vector< int > arr{ -2, -5, 6, -2, -3, 1, 5, -6 }; // Function call SubarrayWithMaxSum(arr); return 0; } // This code is contributed by Tapesh(tapeshdua420) |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to print the elements // of Subarray with maximum sum static void SubarrayWithMaxSum(Vector<Integer> nums) { // Initialize currMax and globalMax // with first value of nums int currMax = nums.get( 0 ), globalMax = nums.get( 0 ); // Initialize endIndex startIndex,globalStartIndex int endIndex = 0 ; int startIndex = 0 , globalMaxStartIndex = 0 ; // Iterate for all the elements of the array for ( int i = 1 ; i < nums.size(); ++i) { // Update currMax and startIndex if (nums.get(i) > nums.get(i) + currMax) { currMax = nums.get(i); startIndex = i; // update the new startIndex } // Update currMax else if (nums.get(i) < nums.get(i) + currMax) { currMax = nums.get(i) + currMax; } // Update globalMax and globalMaxStartIndex if (currMax > globalMax) { globalMax = currMax; endIndex = i; globalMaxStartIndex = startIndex; } } // Printing the elements of subarray with max sum for ( int i = globalMaxStartIndex; i <= endIndex; ++i) { System.out.print(nums.get(i) + " " ); } } // Driver Code public static void main(String[] args) { // Given array arr[] Vector<Integer> arr = new Vector<Integer>(); arr.add(- 2 ); arr.add(- 5 ); arr.add( 6 ); arr.add(- 2 ); arr.add(- 3 ); arr.add( 1 ); arr.add( 5 ); arr.add(- 6 ); // Function call SubarrayWithMaxSum(arr); } } // This code is contributed by Amritha Basavaraj Patil |
Python3
# Python program for the above approach: # Function to print the elements # of Subarray with maximum sum def SubarrayWithMaxSum(nums): # Initialize currMax and globalMax # with first value of nums currMax = nums[ 0 ] globalMax = nums[ 0 ] # Initialize endIndex startIndex,globalStartIndex endIndex = 0 startIndex = 0 globalMaxStartIndex = 0 # Iterate for all the elements of the array for i in range ( 1 , len (nums)): # Update currMax and startIndex if (nums[i] > nums[i] + currMax): currMax = nums[i] startIndex = i # update the new startIndex # Update currMax elif (nums[i] < nums[i] + currMax): currMax + = nums[i] # Update globalMax and globalMaxStartIndex if (currMax > globalMax): globalMax = currMax endIndex = i globalMaxStartIndex = startIndex # Printing the elements of subarray with max sum for i in range (globalMaxStartIndex, endIndex + 1 ): print (nums[i], end = ' ' ) # Driver code if __name__ = = '__main__' : # Given array arr[] arr = [] arr.append( - 2 ) arr.append( - 5 ) arr.append( 6 ) arr.append( - 2 ) arr.append( - 3 ) arr.append( 1 ) arr.append( 5 ) arr.append( - 6 ) # Function call SubarrayWithMaxSum(arr) # This code is contributed by subhamgoyal2014. |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Function to print the elements // of Subarray with maximum sum static void SubarrayWithMaxSum(List< int > nums) { // Initialize currMax and globalMax // with first value of nums int currMax = nums[0], globalMax = nums[0]; // Initialize endIndex startIndex,globalStartIndex int endIndex = 0; int startIndex = 0, globalMaxStartIndex = 0; // Iterate for all the elements of the array for ( int i = 1; i < nums.Count; ++i) { // Update currMax and startIndex if (nums[i] > nums[i] + currMax) { currMax = nums[i]; startIndex = i; // update the new startIndex } // Update currMax else if (nums[i] < nums[i] + currMax) { currMax = nums[i] + currMax; } // Update globalMax and globalMaxStartIndex if (currMax > globalMax) { globalMax = currMax; endIndex = i; globalMaxStartIndex = startIndex; } } // Printing the elements of subarray with max sum for ( int i = globalMaxStartIndex; i <= endIndex; ++i) { Console.Write(nums[i] + " " ); } } // Driver Code static public void Main() { // Given array arr[] List< int > arr = new List< int >(); arr.Add(-2); arr.Add(-5); arr.Add(6); arr.Add(-2); arr.Add(-3); arr.Add(1); arr.Add(5); arr.Add(-6); // Function call SubarrayWithMaxSum(arr); } } // This code is contributed by rag2127. |
Javascript
<script> // JavaScript program for the above approach // Function to print the elements // of Subarray with maximum sum function SubarrayWithMaxSum(nums) { // Initialize currMax and globalMax // with first value of nums let currMax = nums[0], globalMax = nums[0]; // Initialize endIndex startIndex,globalStartIndex let endIndex = 0; let startIndex = 0, globalMaxStartIndex = 0; // Iterate for all the elements of the array for (let i = 1; i < nums.length; ++i) { // Update currMax and startIndex if (nums[i] > nums[i] + currMax) { currMax = nums[i]; startIndex = i; // update the new startIndex } // Update currMax else if (nums[i] < nums[i] + currMax) { currMax = nums[i] + currMax; } // Update globalMax and globalMaxStartIndex if (currMax > globalMax) { globalMax = currMax; endIndex = i; globalMaxStartIndex = startIndex; } } // Printing the elements of subarray with max sum for (let i = globalMaxStartIndex; i <= endIndex; ++i) { document.write(nums[i] + " " ); } } // Driver Code let arr = []; arr.push(-2); arr.push(-5); arr.push(6); arr.push(-2); arr.push(-3); arr.push(1); arr.push(5); arr.push(-6); // Function call SubarrayWithMaxSum(arr); // This code is contributed by unknown2108 </script> |
6 -2 -3 1 5
Time complexity: O(N)
Auxiliary Space: O(1)
Contact Us