Divide the array in K segments such that the sum of minimums is maximized | Python 3 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 been visited already ; 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
MAX = 10 NEW_LINE def maximizeSum ( a , n , ind , k , dp ) : NEW_LINE INDENT if ( k == 0 ) : NEW_LINE INDENT if ( ind == n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT else : NEW_LINE INDENT return - 1e9 NEW_LINE DEDENT DEDENT elif ( ind == n ) : NEW_LINE INDENT return - 1e9 NEW_LINE DEDENT elif ( dp [ ind ] [ k ] != - 1 ) : NEW_LINE INDENT return dp [ ind ] [ k ] NEW_LINE DEDENT else : NEW_LINE INDENT ans = 0 NEW_LINE mini = a [ ind ] NEW_LINE for i in range ( ind , n , 1 ) : NEW_LINE INDENT mini = min ( mini , a [ i ] ) NEW_LINE ans = max ( ans , maximizeSum ( \ a , n , i + 1 , k - 1 , dp ) + mini ) NEW_LINE DEDENT dp [ ind ] [ k ] = ans NEW_LINE return ans NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = [ 5 , 7 , 4 , 2 , 1 , 6 ] NEW_LINE k = 3 NEW_LINE n = len ( a ) NEW_LINE dp = [ [ - 1 for i in range ( MAX ) ] \ for j in range ( MAX ) ] NEW_LINE print ( maximizeSum ( a , n , 0 , k , dp ) ) NEW_LINE DEDENT