Problem Statement :
Given an array Arr[] of N integers. Find the contiguous sub-array(containing at least one number) which has the maximum sum and return its sum.
Input Format:
The first line of input contains an integer ‘N’ denoting the number of array elements.
The second line contains ’N’ consecutive numbers separated by a wide space.
Output Format:
The output contains one line containing the maximum value of the subarray of the given array.
Explanation of Test case:
In the given test case, we see that
Max subarray sum is 9
of elements (1, 2, 3, -2, 5) which
is a contiguous subarray.Approach:
The simple idea of Kadane’s algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far.
