The painter 's partition problem | function to calculate sum between two indices in list ; bottom up tabular dp ; initialize table ; base cases k = 1 ; n = 1 ; 2 to k partitions for i in range ( 2 , k + 1 ) : 2 to n boards ; track minimum ; i - 1 th separator before position arr [ p = 1. . j ] ; required ; Driver Code ; Calculate size of array .
def sum ( arr , start , to ) : NEW_LINE INDENT total = 0 NEW_LINE for i in range ( start , to + 1 ) : NEW_LINE INDENT total += arr [ i ] NEW_LINE DEDENT return total NEW_LINE DEDENT def findMax ( arr , n , k ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( n + 1 ) ] for j in range ( k + 1 ) ] NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT dp [ 1 ] [ i ] = sum ( arr , 0 , i - 1 ) NEW_LINE DEDENT for i in range ( 1 , k + 1 ) : NEW_LINE INDENT dp [ i ] [ 1 ] = arr [ 0 ] NEW_LINE for j in range ( 2 , n + 1 ) : NEW_LINE INDENT best = 100000000 NEW_LINE for p in range ( 1 , j + 1 ) : NEW_LINE INDENT best = min ( best , max ( dp [ i - 1 ] [ p ] , sum ( arr , p , j - 1 ) ) ) NEW_LINE DEDENT dp [ i ] [ j ] = best NEW_LINE DEDENT DEDENT return dp [ k ] [ n ] NEW_LINE DEDENT arr = [ 10 , 20 , 60 , 50 , 30 , 40 ] NEW_LINE n = len ( arr ) NEW_LINE k = 3 NEW_LINE print ( findMax ( arr , n , k ) ) NEW_LINE INDENT n = len ( arr ) NEW_LINE DEDENT k = 3 NEW_LINE print ( findMax ( arr , n , k ) ) NEW_LINE