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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 10 ; int maximizeSum ( int a [ ] , int n , int ind , int k , int dp [ MAX ] [ MAX ] ) { if ( k == 0 ) { if ( ind == n ) return 0 ; else return -1e9 ; } else if ( ind == n ) return -1e9 ; 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 = min ( mini , a [ i ] ) ; ans = max ( ans , maximizeSum ( a , n , i + 1 , k - 1 , dp ) + mini ) ; } return dp [ ind ] [ k ] = ans ; } } int main ( ) { int a [ ] = { 5 , 7 , 4 , 2 , 8 , 1 , 6 } ; int k = 3 ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int dp [ MAX ] [ MAX ] ; memset ( dp , -1 , sizeof dp ) ; cout << maximizeSum ( a , n , 0 , k , dp ) ; return 0 ; }