Design a dynamic program solution to solve the "maximum contiguous subarray" problem, also known as Kadanes Algorithm. That is: given an array arr[] of size N. The task is to find the sum of the contiguous subarray within arr[] with the largest sum.

Your solution should have all the steps of a typical dynamic programming problem. Your algorithm, presented in pseudo-code, should run in a time which is asymptotically better (i.e., faster) than O(n log n). Note that you can also deal with the reconstruction problem here, which simply finds the locations of the beginning and ending indexes of such an array.