#codingexercise
Yesterday we were discussing finding largest sum sub-matrix. It required largest sum subarray to be efficient. This we have seen earlier as Kadane's algorithm. Today we require to compute k such maximum sum subarray that are non-overlapping. The approach in this case is
repeat for k times :
   First find a subarray with maximum sum using techniques discussed earlier.
   If such an array exists:
         print the bounds of the subarray along with its sum
         replace this subarray with values lower than all elements so that it does not participate in the next find.
Note that the existence of the array might fail because there might not be k such subarray. Each iteration is greedy and inclusive of as many contiguous elements as possible. If the number of such arrays fall short of k, we can always slice the arrays to meet or exceed k based on the descending order of subarrays ordered by their sum.
   We discuss the ways to find the max subarray sum:
Largest subarray sum - Kadane’s algorithm

Initialize 

max_so_far = 0

max_ending_here = 0

For each element of the array

                max_ending_here = max(0, max_ending_here+ A[i])

                max_so_far  = max(max_so_far, max_ending_here)

Alternatively

Initialize and maintain the following variables

x = sum of elements

y = minimum of sum encountered

z = maximum of sum encountered

For each element of the array

           y = min(x, y)

           z = max(z, x-y)
 return s

For example:

-1, 0, 2, 1 array
has following x, y, and z values in each iteration:
      x     y   z
      -1   -1   0
      -1   -1   0
       1   -1   2
       2   -1   3
max sub array sum = 3