We use Kadane 's algorithm to fill maxSum[]  Below code is taken from method3 of  https:www.geeksforgeeks.org/largest-sum-contiguous-subarray/
curr_max = a [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT curr_max = max ( a [ i ] , curr_max + a [ i ] ) NEW_LINE maxSum [ i ] = curr_max NEW_LINE DEDENT