We use Kadane 's algorithm  to fill maxSum[]
$ curr_max = $ a [ 0 ] ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) { $ curr_max = max ( $ a [ $ i ] , $ curr_max + $ a [ $ i ] ) ; $ maxSum [ $ i ] = $ curr_max ; }