Divide an array into K subarray with the given condition | Function to divide an array into k parts such that the summ 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 summ ; Run a loop from i to n ; Find the maximum number from i to l and the summ from i to l ; Find the summ of difference of every element with the maximum element ; If the array can be divided ; Returns the minimum summ in K parts ; Driver code
def divideArray ( arr , n , k ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( 500 ) ] for i in range ( 500 ) ] NEW_LINE k -= 1 NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT for j in range ( 0 , k + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = 10 ** 9 NEW_LINE max_ = - 1 NEW_LINE summ = 0 NEW_LINE for l in range ( i , n ) : NEW_LINE INDENT max_ = max ( max_ , arr [ l ] ) NEW_LINE summ += arr [ l ] NEW_LINE diff = ( l - i + 1 ) * max_ - summ NEW_LINE if ( j > 0 ) : NEW_LINE INDENT dp [ i ] [ j ] = min ( dp [ i ] [ j ] , diff + dp [ l + 1 ] [ j - 1 ] ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = diff NEW_LINE DEDENT DEDENT DEDENT DEDENT return dp [ 0 ] [ k ] NEW_LINE DEDENT arr = [ 2 , 9 , 5 , 4 , 8 , 3 , 6 ] NEW_LINE n = len ( arr ) NEW_LINE k = 2 NEW_LINE print ( divideArray ( arr , n , k ) ) NEW_LINE