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
int maxRightSubArraySum ( int a [ ] , int n , int sum [ ] ) { int max_so_far = a [ n ] ; int curr_max = a [ n ] ; sum [ n ] = max_so_far ; for ( int 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 ; }