Trapping Rain Water | Method to find maximum amount of water that can be trapped within given set of bars . ; initialize output ; maximum element on left and right ; indices to traverse the array ; update max in left ; water on curr element = max - curr ; update right maximum ; Driver Code
< ? php function findWater ( $ arr , $ n ) { $ result = 0 ; $ left_max = 0 ; $ right_max = 0 ; $ lo = 0 ; $ hi = $ n - 1 ; while ( $ lo <= $ hi ) { if ( $ arr [ $ lo ] < $ arr [ $ hi ] ) { if ( $ arr [ $ lo ] > $ left_max ) $ left_max = $ arr [ $ lo ] ; else $ result += $ left_max - $ arr [ $ lo ] ; $ lo ++ ; } else { if ( $ arr [ $ hi ] > $ right_max ) $ right_max = $ arr [ $ hi ] ; else $ result += $ right_max - $ arr [ $ hi ] ; $ hi -- ; } } return $ result ; } $ arr = array ( 0 , 1 , 0 , 2 , 1 , 0 , 1 , 3 , 2 , 1 , 2 , 1 ) ; $ n = count ( $ arr ) ; echo " Maximum ▁ water ▁ that ▁ can ▁ be ▁ accumulated ▁ is ▁ " , findWater ( $ arr , $ n ) ; ? >