The painter 's partition problem | function to calculate sum between two indices in array ; bottom up tabular dp ; initialize table ; base cases k = 1 ; n = 1 ; 2 to k partitions ; track minimum ; i - 1 th separator before position arr [ p = 1. . j ] ; required ; Driver Code ; Calculate size of array .
< ? php function sum ( $ arr , $ from , $ to ) { $ total = 0 ; for ( $ i = $ from ; $ i <= $ to ; $ i ++ ) $ total += $ arr [ $ i ] ; return $ total ; } function findMax ( $ arr , $ n , $ k ) { $ dp [ $ k + 1 ] [ $ n + 1 ] = array ( 0 ) ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) $ dp [ 1 ] [ $ i ] = sum ( $ arr , 0 , $ i - 1 ) ; for ( $ i = 1 ; $ i <= $ k ; $ i ++ ) $ dp [ $ i ] [ 1 ] = $ arr [ 0 ] ; for ( $ i = 2 ; $ i <= $ k ; $ i ++ ) { $ best = PHP_INT_MAX ; for ( $ p = 1 ; $ p <= $ j ; $ p ++ ) $ best = min ( $ best , max ( $ dp [ $ i - 1 ] [ $ p ] , sum ( $ arr , $ p , $ j - 1 ) ) ) ; $ dp [ $ i ] [ $ j ] = $ best ; } } return $ dp [ $ k ] [ $ n ] ; } $ arr = array ( 10 , 20 , 60 , 50 , 30 , 40 ) ; $ n = sizeof ( $ arr ) ; $ k = 3 ; echo findMax ( $ arr , $ n , $ k ) , " STRNEWLINE " ; ? >