Find Largest Sum Contiguous Subarray – Kadane’s algorithm

Write a program to find largest sum contiguous subarray. Given an array of N elements, find the maximum possible sum of a contiguous subarray. An array can contain both positive and negative values.

For example –

Let’s take an array¬†whose values are { 1, 2, -5, 4, 3, 8 , 5 }

The maximum sum of a subarray in this array is 20.  And the subarray is (4, 3, 8, 5).