Find maximum subarray sum for subarray [ i . . n ] using Kadane ' s ▁ algorithm . ▁ This ▁ ▁ version ▁ of ▁ Kadane ' s Algorithm will work if all numbers are negative
function maxRightSubArraySum ( & $ a , $ n , & $ sum ) { $ max_so_far = $ a [ $ n ] ; $ curr_max = $ a [ $ n ] ; $ sum [ $ n ] = $ max_so_far ; for ( $ i = $ n - 1 ; $ i >= 0 ; $ i -- ) { $ curr_max = max ( $ a [ $ i ] , $ curr_max + $ a [ $ i ] ) ; $ max_so_far = max ( $ max_so_far , $ curr_max ) ; $ sum [ $ i ] = $ max_so_far ; } return $ max_so_far ; }