Kadane’s Algorithm is a Linear Time Algorithm which aims to find the maximum sum of a contiguous sub array of any array.

For eg. In this array { -1, -3, 4,-1 , 5 } . The Maximum sum of the sub array is 8. The Sub array with the maximumu sum is { 4 , -1 , 5 }.

## Code :

## Output :