Maximum subarray problem

Problem Statement

Finding a contiguous sub-array which has the largest sum in an 1-D array.

Algorithm

This problem is solved by using Kadane Algorithm. This algorithm is a linear time algorithm.