Maximum subarray sum in O ( n ) using prefix sum | Function to compute maximum subarray sum in linear time . ; Initialize minimum prefix sum to 0. ; Initialize maximum subarray sum so far to - infinity . ; Initialize and compute the prefix sum array . ; loop through the array , keep track of minimum prefix sum so far and maximum subarray sum . ; Test case 1 ; Test case 2
< ? php function maximumSumSubarray ( $ arr , $ n ) { $ min_prefix_sum = 0 ; $ res = PHP_INT_MIN ; $ prefix_sum = array ( ) ; $ prefix_sum [ 0 ] = $ arr [ 0 ] ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) $ prefix_sum [ $ i ] = $ prefix_sum [ $ i - 1 ] + $ arr [ $ i ] ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { $ res = max ( $ res , $ prefix_sum [ $ i ] - $ min_prefix_sum ) ; $ min_prefix_sum = min ( $ min_prefix_sum , $ prefix_sum [ $ i ] ) ; } return $ res ; } $ arr1 = array ( -2 , -3 , 4 , -1 , -2 , 1 , 5 , -3 ) ; $ n1 = count ( $ arr1 ) ; echo maximumSumSubarray ( $ arr1 , $ n1 ) , " " ; $ arr2 = array ( 4 , -8 , 9 , -4 , 1 , -8 , -1 , 6 ) ; $ n2 = count ( $ arr2 ) ; echo maximumSumSubarray ( $ arr2 , $ n2 ) ; ? >