We use Kadane 's algorithm to fill maxSum[]  Below code is taken from method 3 of  https:www.geeksforgeeks.org/largest-sum-contiguous-subarray/
int curr_max = a [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) { curr_max = max ( a [ i ] , curr_max + a [ i ] ) ; maxSum [ i ] = curr_max ; }