Possible cuts of a number such that maximum parts are divisible by 3 | Function to find the maximum number of numbers divisible by 3 in a large number ; store size of the string ; Stores last index of a remainder ; last visited place of remainder zero is at 0. ; To store result from 0 to i ; get the remainder ; Get maximum res [ i ] value ; Driver Code
< ? php function MaximumNumbers ( $ s ) { $ n = strlen ( $ s ) ; $ remIndex = array_fill ( 0 , 3 , -1 ) ; $ remIndex [ 0 ] = 0 ; $ res = array ( ) ; $ r = 0 ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) { $ r = ( $ r + $ s [ $ i - 1 ] - '0' ) % 3 ; $ res [ $ i ] = $ res [ $ i - 1 ] ; if ( $ remIndex [ $ r ] != -1 ) $ res [ $ i ] = max ( $ res [ $ i ] , $ res [ $ remIndex [ $ r ] ] + 1 ) ; $ remIndex [ $ r ] = $ i + 1 ; } return $ res [ $ n ] ; } $ s = "12345" ; print ( MaximumNumbers ( $ s ) ) # This  code is contributed by Ryuga NEW_LINE ? >