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 for ( let i = 2 ; i <= k ; i ++ ) { 2 to n boards ; track minimum ; i - 1 th separator before position arr [ p = 1. . j ] ; required ; Driver code ; Calculate size of array .
function sum ( arr , from , to ) { let total = 0 ; for ( let i = from ; i <= to ; i ++ ) total += arr [ i ] ; return total ; } function findMax ( arr , n , k ) { let dp = new Array ( k + 1 ) ; for ( let i = 0 ; i < k + 1 ; i ++ ) { dp [ i ] = new Array ( n + 1 ) ; } for ( let i = 1 ; i <= n ; i ++ ) dp [ 1 ] [ i ] = sum ( arr , 0 , i - 1 ) ; for ( let i = 1 ; i <= k ; i ++ ) dp [ i ] [ 1 ] = arr [ 0 ] ; for ( let j = 2 ; j <= n ; j ++ ) { let best = Number . MAX_VALUE ; for ( let p = 1 ; p <= j ; p ++ ) best = Math . min ( best , Math . max ( dp [ i - 1 ] [ p ] , sum ( arr , p , j - 1 ) ) ) ; dp [ i ] [ j ] = best ; } } return dp [ k ] [ n ] ; } let arr = [ 10 , 20 , 60 , 50 , 30 , 40 ] ; let n = arr . length ; let k = 3 ; document . write ( findMax ( arr , n , k ) ) ;