Divide an array into K subarray with the given condition | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int divideArray ( int arr [ ] , int n , int k ) { int dp [ 500 ] [ 500 ] = { 0 } ; k -= 1 ; for ( int i = n - 1 ; i >= 0 ; i -- ) { for ( int j = 0 ; j <= k ; j ++ ) { dp [ i ] [ j ] = INT_MAX ; int max_ = -1 , sum = 0 ; for ( int l = i ; l < n ; l ++ ) { max_ = max ( max_ , arr [ l ] ) ; sum += arr [ l ] ; int diff = ( l - i + 1 ) * max_ - sum ; if ( j > 0 ) dp [ i ] [ j ] = min ( dp [ i ] [ j ] , diff + dp [ l + 1 ] [ j - 1 ] ) ; else dp [ i ] [ j ] = diff ; } } } return dp [ 0 ] [ k ] ; } int main ( ) { int arr [ ] = { 2 , 9 , 5 , 4 , 8 , 3 , 6 } ; int n = sizeof ( arr ) / sizeof ( int ) ; int k = 2 ; cout << divideArray ( arr , n , k ) << " STRNEWLINE " ; return 0 ; }