Divide the array in K segments such that the sum of minimums is maximized | C # program to find the sum of the minimum of all the segments ; Function to maximize the sum of the minimums ; If k segments have been divided ; If we are at the end ; If we donot reach the end then return a negative number that cannot be the sum ; If at the end but k segments are not formed ; If the state has not been visited yet ; If the state has not been visited ; Get the minimum element in the segment ; Iterate and try to break at every index and create a segment ; Find the minimum element in the segment ; Find the sum of all the segments trying all the possible combinations ; Return the answer by memoizing it ; Driver Code ; Initialize dp array with - 1
using System ; class GFG { static int MAX = 10 ; public static int maximizeSum ( int [ ] a , int n , int ind , int k , int [ ] dp ) { if ( k == 0 ) { if ( ind == n ) return 0 ; else return - 1000000000 ; } else if ( ind == n ) return - 1000000000 ; else if ( dp [ ind , k ] != - 1 ) return dp [ ind , k ] ; else { int ans = 0 ; int mini = a [ ind ] ; for ( int i = ind ; i < n ; i ++ ) { mini = Math . Min ( mini , a [ i ] ) ; ans = Math . Max ( ans , maximizeSum ( a , n , i + 1 , k - 1 , dp ) + mini ) ; } return dp [ ind , k ] = ans ; } } public static void Main ( String [ ] args ) { int [ ] a = { 5 , 7 , 4 , 2 , 8 , 1 , 6 } ; int k = 3 ; int n = a . Length ; int [ , ] dp = new int [ MAX , MAX ] ; for ( int i = 0 ; i < MAX ; i ++ ) { for ( int j = 0 ; j < MAX ; j ++ ) dp [ i , j ] = - 1 ; } Console . WriteLine ( maximizeSum ( a , n , 0 , k , dp ) ) ; } }