Divide an array into K subarray with the given condition | Java implementation of the above approach ; Function to divide an array into k parts such that the sum of difference of every element with the maximum element of that part is minimum ; Dp to store the values ; Fill up the dp table ; Intitilize maximum value ; Max element and the sum ; Run a loop from i to n ; Find the maximum number from i to l and the sum from i to l ; Find the sum of difference of every element with the maximum element ; If the array can be divided ; Returns the minimum sum in K parts ; Driver code
class GFG { static int divideArray ( int arr [ ] , int n , int k ) { int dp [ ] [ ] = new int [ 500 ] [ 500 ] ; int i , j ; for ( i = 0 ; i < 500 ; i ++ ) for ( j = 0 ; j < 500 ; j ++ ) dp [ i ] [ j ] = 0 ; k -= 1 ; for ( i = n - 1 ; i >= 0 ; i -- ) { for ( j = 0 ; j <= k ; j ++ ) { dp [ i ] [ j ] = Integer . MAX_VALUE ; int max_ = - 1 , sum = 0 ; for ( int l = i ; l < n ; l ++ ) { max_ = Math . max ( max_ , arr [ l ] ) ; sum += arr [ l ] ; int diff = ( l - i + 1 ) * max_ - sum ; if ( j > 0 ) dp [ i ] [ j ] = Math . min ( dp [ i ] [ j ] , diff + dp [ l + 1 ] [ j - 1 ] ) ; else dp [ i ] [ j ] = diff ; } } } return dp [ 0 ] [ k ] ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 9 , 5 , 4 , 8 , 3 , 6 } ; int n = arr . length ; int k = 2 ; System . out . println ( divideArray ( arr , n , k ) ) ; } }