Print continuous subarray with maximum sum

Given an array of integers, find and print contiguous subarray with maximum sum in it.

 

For example,


Input:  {-2, 1, -3, 4, -1, 2, 1, -5, 4}

Output: The contiguous subarray with the largest sum is {4, -1, 2, 1}
 

Input:  {8, -7, -3, 5, 6, -2, 3, -4, 2}

Output: The contiguous subarray with the largest sum is {5, 6, -2, 3}

 

 
We can easily solve this problem in linear time using Kadane’s algorithm by maintaining maximum sum subarray ending at each index of the array. Then this subarray is –

  • either empty in which case its sum is zero or
     
  • consists of one more element than the maximum subarray ending at the previous index
     

We have already discussed this approach here that only output the sum of contiguous subarray having the largest sum but do not print the subarray itself. We can easily modify the algorithm to keep track of the starting and ending indices of the maximum subarray.

C++

Download   Run Code

Java

Download   Run Code

Output:

The sum of contiguous subarray with the largest sum is 6
The contiguous subarray with the largest sum is 4 -1 2 1

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Vishwajeet
Guest

The code will not work if all elements are negative..
See this approach this can handle negative elements as well..
https://ideone.com/chOUZq