Split array into subarrays at minimum cost by minimizing count of repeating elements in each subarray | Java program for the above approach ; Function to find the minimum cost of splitting the array into subarrays ; Get the maximum element ; dp [ ] will store the minimum cost upto index i ; Initialize the result array ; Initialise the first element ; Create the frequency array ; Update the frequency ; Counting the cost of the duplicate element ; Minimum cost of operation from 0 to j ; Total cost of the array ; Driver Code ; Given cost K ; Function Call
import java . util . * ; class GFG { static long findMinCost ( int [ ] a , int k , int n ) { int max_ele = Arrays . stream ( a ) . max ( ) . getAsInt ( ) ; long [ ] dp = new long [ n + 1 ] ; for ( int i = 1 ; i <= n ; ++ i ) dp [ i ] = Integer . MAX_VALUE ; dp [ 0 ] = 0 ; for ( int i = 0 ; i < n ; ++ i ) { int [ ] freq = new int [ max_ele + 1 ] ; for ( int j = i ; j < n ; ++ j ) { freq [ a [ j ] ] ++ ; int cost = 0 ; for ( int x = 0 ; x <= max_ele ; ++ x ) { cost += ( freq [ x ] == 1 ) ? 0 : freq [ x ] ; } dp [ j + 1 ] = Math . min ( dp [ i ] + cost + k , dp [ j + 1 ] ) ; } } return dp [ n ] ; } public static void main ( String [ ] args ) { int [ ] arr = { 1 , 2 , 1 , 1 , 1 } ; int K = 2 ; int n = arr . length ; System . out . print ( findMinCost ( arr , K , n ) ) ; } }