Divide an array into K subarray with the given condition | 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
function divideArray ( arr , n , k ) { var dp = Array . from ( Array ( 500 ) , ( ) => Array ( 500 ) . fill ( 0 ) ) ; k -= 1 ; for ( var i = n - 1 ; i >= 0 ; i -- ) { for ( var j = 0 ; j <= k ; j ++ ) { dp [ i ] [ j ] = 1000000000 ; var max_ = - 1 , sum = 0 ; for ( var l = i ; l < n ; l ++ ) { max_ = Math . max ( max_ , arr [ l ] ) ; sum += arr [ l ] ; var 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 ] ; } var arr = [ 2 , 9 , 5 , 4 , 8 , 3 , 6 ] ; var n = arr . length ; var k = 2 ; document . write ( divideArray ( arr , n , k ) + " " ) ;