Split a given array into K subarrays minimizing the difference between their maximum and minimum | C ++ program for the above approach ; Function to find the subarray ; Add the difference to vectors ; Sort vector to find minimum k ; Initialize result ; Adding first k - 1 values ; Return the minimized sum ; Driver Code ; Given array arr [ ] ; Given K ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int find ( int a [ ] , int n , int k ) { vector < int > v ; for ( int i = 1 ; i < n ; ++ i ) { v . push_back ( a [ i - 1 ] - a [ i ] ) ; } sort ( v . begin ( ) , v . end ( ) ) ; int res = a [ n - 1 ] - a [ 0 ] ; for ( int i = 0 ; i < k - 1 ; ++ i ) { res += v [ i ] ; } return res ; } int main ( ) { int arr [ ] = { 4 , 8 , 15 , 16 , 23 , 42 } ; int N = sizeof ( arr ) / sizeof ( int ) ; int K = 3 ; cout << find ( arr , N , K ) << endl ; return 0 ; }