The painter 's partition problem | A DP based C # program for 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 ( int 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 .
using System ; class GFG { static int sum ( int [ ] arr , int from , int to ) { int total = 0 ; for ( int i = from ; i <= to ; i ++ ) total += arr [ i ] ; return total ; } static int findMax ( int [ ] arr , int n , int k ) { int [ , ] dp = new int [ k + 1 , n + 1 ] ; for ( int i = 1 ; i <= n ; i ++ ) dp [ 1 , i ] = sum ( arr , 0 , i - 1 ) ; for ( int i = 1 ; i <= k ; i ++ ) dp [ i , 1 ] = arr [ 0 ] ; for ( int j = 2 ; j <= n ; j ++ ) { int best = int . MaxValue ; for ( int 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 ] ; } public static void ( ) { int [ ] arr = { 10 , 20 , 60 , 50 , 30 , 40 } ; int n = arr . Length ; int k = 3 ; Console . WriteLine ( findMax ( arr , n , k ) ) ; } }