Maximum Subarray Sum after inverting at most two elements | Function to return the maximum required sub - array sum ; Creating one based indexing ; 2d array to contain solution for each step ; Case 1 : Choosing current or ( current + previous ) whichever is smaller ; Case 2 : ( a ) Altering sign and add to previous case 1 or value 0 ; Case 2 : ( b ) Adding current element with previous case 2 and updating the maximum ; Case 3 : ( a ) Altering sign and add to previous case 2 ; Case 3 : ( b ) Adding current element with previous case 3 ; Updating the maximum value of variable ans ; Return the final solution ; Driver code
< ? php function maxSum ( $ a , $ n ) { $ ans = 0 ; $ arr = array ( ) ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) $ arr [ $ i ] = $ a [ $ i - 1 ] ; $ dp = array ( array ( ) ) ; for ( $ i = 1 ; $ i <= $ n ; ++ $ i ) { $ dp [ $ i ] [ 0 ] = max ( $ arr [ $ i ] , $ dp [ $ i - 1 ] [ 0 ] + $ arr [ $ i ] ) ; $ dp [ $ i ] [ 1 ] = max ( 0 , $ dp [ $ i - 1 ] [ 0 ] ) - $ arr [ $ i ] ; if ( $ i >= 2 ) $ dp [ $ i ] [ 1 ] = max ( $ dp [ $ i ] [ 1 ] , $ dp [ $ i - 1 ] [ 1 ] + $ arr [ $ i ] ) ; if ( $ i >= 2 ) $ dp [ $ i ] [ 2 ] = $ dp [ $ i - 1 ] [ 1 ] - $ arr [ $ i ] ; if ( $ i >= 3 ) $ dp [ $ i ] [ 2 ] = max ( $ dp [ $ i ] [ 2 ] , $ dp [ $ i - 1 ] [ 2 ] + $ arr [ $ i ] ) ; $ ans = max ( $ ans , $ dp [ $ i ] [ 0 ] ) ; $ ans = max ( $ ans , $ dp [ $ i ] [ 1 ] ) ; $ ans = max ( $ ans , $ dp [ $ i ] [ 2 ] ) ; } return $ ans ; } $ arr = array ( -5 , 3 , 2 , 7 , -8 , 3 , 7 , -9 , 10 , 12 , -6 ) ; $ n = count ( $ arr ) ; echo maxSum ( $ arr , $ n ) ; ? >