Dada una array a de tamaño N y un número entero K , la tarea es dividir la array en K segmentos de modo que la suma del mínimo de K segmentos se maximice.
Ejemplos:
Entrada: a[] = {5, 7, 4, 2, 8, 1, 6}, K = 3
Salida: 7
Divide la array en los índices 0 y 1. Entonces los segmentos son {5}, {7}, { 4, 2, 8, 1, 6}. La suma del mínimo es 5 + 7 + 1 = 13
Entrada: a[] = {6, 5, 3, 8, 9, 10, 4, 7, 10}, K = 4
Salida: 27
Enfoque : El problema se puede resolver usando Programación Dinámica . Pruebe todas las particiones posibles que son posibles usando recursividad . Sea dp[i][k] la suma máxima de los mínimos hasta el índice i con k particiones. Por lo tanto, los posibles estados se dividirán en cada índice desde el índice i hasta el n. La suma máxima de los mínimos de todos esos estados será nuestra respuesta. Después de escribir esta recurrencia, podemos usar la memorización.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the sum of // the minimum of all the segments #include <bits/stdc++.h> using namespace std; const int MAX = 10; // Function to maximize the sum of the minimums int maximizeSum(int a[], int n, int ind, int k, int dp[MAX][MAX]) { // If k segments have been divided if (k == 0) { // If we are at the end if (ind == n) return 0; // If we donot reach the end // then return a negative number // that cannot be the sum else return -1e9; } // If at the end but // k segments are not formed else if (ind == n) return -1e9; // If the state has not been visited yet else if (dp[ind][k] != -1) return dp[ind][k]; // If the state has not been visited else { int ans = 0; // Get the minimum element in the segment int mini = a[ind]; // Iterate and try to break at every index // and create a segment for (int i = ind; i < n; i++) { // Find the minimum element in the segment mini = min(mini, a[i]); // Find the sum of all the segments trying all // the possible combinations ans = max(ans, maximizeSum( a, n, i + 1, k - 1, dp) + mini); } // Return the answer by // memoizing it return dp[ind][k] = ans; } } // Driver Code int main() { int a[] = { 5, 7, 4, 2, 8, 1, 6 }; int k = 3; int n = sizeof(a) / sizeof(a[0]); // Initialize dp array with -1 int dp[MAX][MAX]; memset(dp, -1, sizeof dp); cout << maximizeSum(a, n, 0, k, dp); return 0; }
Java
// Java program to find the sum of // the minimum of all the segments class GFG { static int MAX = 10; // Function to maximize the // sum of the minimums public static int maximizeSum( int[] a, int n, int ind, int k, int[][] dp) { // If k segments have been divided if (k == 0) { // If we are at the end if (ind == n) return 0; // If we donot reach the end // then return a negative number // that cannot be the sum else return -1000000000; } // If at the end but // k segments are not formed else if (ind == n) return -1000000000; // If the state has not // been visited yet else if (dp[ind][k] != -1) return dp[ind][k]; // If the state has // not been visited else { int ans = 0; // Get the minimum // element in the segment int mini = a[ind]; // Iterate and try to break // at every index // and create a segment for (int i = ind; i < n; i++) { // Find the minimum element // in the segment mini = Math.min(mini, a[i]); // Find the sum of all the // segments trying all // the possible combinations ans = Math.max(ans, maximizeSum(a, n, i + 1, k - 1, dp) + mini); } // Return the answer by // memoizing it return dp[ind][k] = ans; } } // Driver Code public static void main(String[] args) { int[] a = { 5, 7, 4, 2, 8, 1, 6 }; int k = 3; int n = a.length; // Initialize dp array with -1 int[][] dp = new int[MAX][MAX]; for (int i = 0; i < MAX; i++) { for (int j = 0; j < MAX; j++) dp[i][j] = -1; } System.out.println( maximizeSum(a, n, 0, k, dp)); } } // This code is contributed by // sanjeev2552
Python3
# Python 3 program to find the sum of # the minimum of all the segments MAX = 10 # Function to maximize the # sum of the minimums def maximizeSum(a,n, ind, k, dp): # If k segments have been divided if (k == 0): # If we are at the end if (ind == n): return 0 # If we donot reach the end # then return a negative number # that cannot be the sum else: return -1e9 # If at the end but # k segments are not formed elif (ind == n): return -1e9 # If the state has been visited already elif (dp[ind][k] != -1): return dp[ind][k] # If the state has not been visited else: ans = 0 # Get the minimum element # in the segment mini = a[ind] # Iterate and try to break # at every index # and create a segment for i in range(ind,n,1): # Find the minimum element # in the segment mini = min(mini, a[i]) # Find the sum of all the # segments trying all # the possible combinations ans = max(ans, maximizeSum(\ a, n, i + 1, k - 1, dp) + mini) # Return the answer by # memoizing it dp[ind][k] = ans return ans # Driver Code if __name__ == '__main__': a = [5, 7, 4, 2, 1, 6] k = 3 n = len(a) # Initialize dp array with -1 dp = [[-1 for i in range(MAX)]\ for j in range(MAX)] print(maximizeSum(a, n, 0, k, dp)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find the sum of // the minimum of all the segments using System; class GFG { static int MAX = 10; // Function to maximize the sum of the minimums public static int maximizeSum( int[] a, int n, int ind, int k, int[] dp) { // If k segments have been divided if (k == 0) { // If we are at the end if (ind == n) return 0; // If we donot reach the end // then return a negative number // that cannot be the sum else return -1000000000; } // If at the end but // k segments are not formed else if (ind == n) return -1000000000; // If the state has not // been visited yet else if (dp[ind, k] != -1) return dp[ind, k]; // If the state has not been visited else { int ans = 0; // Get the minimum element // in the segment int mini = a[ind]; // Iterate and try to break // at every index // and create a segment for (int i = ind; i < n; i++) { // Find the minimum element // in the segment mini = Math.Min(mini, a[i]); // Find the sum of all the // segments trying all // the possible combinations ans = Math.Max(ans, maximizeSum(a, n, i + 1, k - 1, dp) + mini); } // Return the answer by // memoizing it return dp[ind,k] = ans; } } // Driver Code public static void Main(String[] args) { int[] a = { 5, 7, 4, 2, 8, 1, 6 }; int k = 3; int n = a.Length; // Initialize dp array with -1 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)); } } // This code is contributed by 29AjayKumar
Javascript
<script> // JavaScript program to find the sum of // the minimum of all the segments var MAX = 10; // Function to maximize the // sum of the minimums function maximizeSum(a , n , ind , k, dp) { // If k segments have been divided if (k == 0) { // If we are at the end if (ind == n) return 0; // If we donot reach the end // then return a negative number // that cannot be the sum else return -1000000000; } // If at the end but // k segments are not formed else if (ind == n) return -1000000000; // If the state has not // been visited yet else if (dp[ind][k] != -1) return dp[ind][k]; // If the state has // not been visited else { var ans = 0; // Get the minimum // element in the segment var mini = a[ind]; // Iterate and try to break // at every index // and create a segment for (i = ind; i < n; i++) { // Find the minimum element // in the segment mini = Math.min(mini, a[i]); // Find the sum of all the // segments trying all // the possible combinations ans = Math.max(ans, maximizeSum(a, n, i + 1, k - 1, dp) + mini); } // Return the answer by // memoizing it return dp[ind][k] = ans; } } // Driver Code var a = [ 5, 7, 4, 2, 8, 1, 6 ]; var k = 3; var n = a.length; // Initialize dp array with -1 var dp = Array(MAX).fill().map(()=>Array(MAX).fill(0)); for (var i = 0; i < MAX; i++) { for (j = 0; j < MAX; j++) dp[i][j] = -1; } document.write(maximizeSum(a, n, 0, k, dp)); // This code contributed by Rajput-Ji </script>
13
Complejidad de tiempo : O(N * N * K)
Espacio auxiliar : O(N * K)