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++ implementation –
 

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

Notify of
avatar
wpDiscuz