This Python program returns the maximum sum of a contiguous sub-array, the start and end index of the sub-array, and the maximum sum of the non-contiguous sub-array.
Kadane’s algorithm is implemented here, which is a linear time, O(n) algorithm.