n 个数组中升序元素的最大和 · GeeksForGeeks 中文系列教程

# n 个数组中升序元素的最大和 > 原文： [https://www.geeksforgeeks.org/maximum-sum-increasing-order-elements-n-arrays/](https://www.geeksforgeeks.org/maximum-sum-increasing-order-elements-n-arrays/) 给定 n 个大小为 m 的数组。找出通过从每个数组中选择一个数字获得的最大和，以使从第 i 个数组中选择的元素大于从第（i-1）个数组中选择的元素。如果无法获得最大和，则返回 0。 **示例**： ``` Input : arr[][] = {{1, 7, 3, 4}, {4, 2, 5, 1}, {9, 5, 1, 8}} Output : 18 Explanation : We can select 4 from first array, 5 from second array and 9 from third array. Input : arr[][] = {{9, 8, 7}, {6, 5, 4}, {3, 2, 1}} Output : 0 ``` 这个想法是从最后一个数组开始选择。我们从最后一个数组中选择最大元素，然后移至倒数第二个数组。在倒数第二个数组中，我们找到最大元素，该元素小于从最后一个数组中选取的最大元素。我们重复此过程，直到到达第一个数组。为了获得最大的总和，我们可以对所有数组进行排序，并从下到上从右到左遍历每个数组，并选择一个大于前一个元素的数字。如果我们不能从数组中选择一个元素，则返回 0。 ## C++ ```cpp // CPP program to find maximum sum // by selecting a element from n arrays #include <bits/stdc++.h> #define M 4 using namespace std; // To calculate maximum sum by // selecting element from each array int maximumSum(int a[][M], int n) { // Sort each array for (int i = 0; i < n; i++) sort(a[i], a[i] + M); // Store maximum element // of last array int sum = a[n - 1][M - 1]; int prev = a[n - 1][M - 1]; int i, j; // Selecting maximum element from // previoulsy selected element for (i = n - 2; i >= 0; i--) { for (j = M - 1; j >= 0; j--) { if (a[i][j] < prev) { prev = a[i][j]; sum += prev; break; } } // j = -1 means no element is // found in a[i] so return 0 if (j == -1) return 0; } return sum; } // Driver program to test maximumSum int main() { int arr[][M] = {{1, 7, 3, 4}, {4, 2, 5, 1}, {9, 5, 1, 8}}; int n = sizeof(arr) / sizeof(arr[0]); cout << maximumSum(arr, n); return 0; } ``` ## Java ```java // Java program to find // maximum sum by selecting // a element from n arrays import java.io.*; class GFG { static int M = 4; static int arr[][] = {{1, 7, 3, 4}, {4, 2, 5, 1}, {9, 5, 1, 8}}; static void sort(int a[][], int row, int n) { for (int i = 0; i < M - 1; i++) { if(a[row][i] > a[row][i + 1]) { int temp = a[row][i]; a[row][i] = a[row][i + 1]; a[row][i + 1] = temp; } } } // To calculate maximum // sum by selecting element // from each array static int maximumSum(int a[][], int n) { // Sort each array for (int i = 0; i < n; i++) sort(a, i, n); // Store maximum element // of last array int sum = a[n - 1][M - 1]; int prev = a[n - 1][M - 1]; int i, j; // Selecting maximum element // from previoulsy selected // element for (i = n - 2; i >= 0; i--) { for (j = M - 1; j >= 0; j--) { if (a[i][j] < prev) { prev = a[i][j]; sum += prev; break; } } // j = -1 means no element // is found in a[i] so // return 0 if (j == -1) return 0; } return sum; } // Driver Code public static void main(String args[]) { int n = arr.length; System.out.print(maximumSum(arr, n)); } } // This code is contributed by // Manish Shaw(manishshaw1) ``` ## Python3 ```py # Python3 program to find # maximum sum by selecting # a element from n arrays M = 4; # To calculate maximum sum # by selecting element from # each array def maximumSum(a, n) : global M; # Sort each array for i in range(0, n) : a[i].sort(); # Store maximum element # of last array sum = a[n - 1][M - 1]; prev = a[n - 1][M - 1]; # Selecting maximum # element from previoulsy # selected element for i in range(n - 2, -1, -1) : for j in range(M - 1, -1, -1) : if (a[i][j] < prev) : prev = a[i][j]; sum += prev; break; # j = -1 means no element # is found in a[i] so # return 0 if (j == -1) : return 0; return sum; # Driver Code arr = [[1, 7, 3, 4], [4, 2, 5, 1], [9, 5, 1, 8]]; n = len(arr) ; print (maximumSum(arr, n)); # This code is contributed by # Manish Shaw(manishshaw1) ``` ## C# ```cs // C# program to find maximum // sum by selecting a element // from n arrays using System; class GFG { static int M = 4; static void sort(ref int[,] a, int row, int n) { for (int i = 0; i < M-1; i++) { if(a[row, i] > a[row, i + 1]) { int temp = a[row, i]; a[row, i] = a[row, i + 1]; a[row, i + 1] = temp; } } } // To calculate maximum // sum by selecting // element from each array static int maximumSum(int[,] a, int n) { int i = 0, j = 0; // Sort each array for (i = 0; i < n; i++) sort(ref a, i, n); // Store maximum element // of last array int sum = a[n - 1, M - 1]; int prev = a[n - 1, M - 1]; // Selecting maximum element // from previoulsy selected // element for (i = n - 2; i >= 0; i--) { for (j = M - 1; j >= 0; j--) { if (a[i, j] < prev) { prev = a[i, j]; sum += prev; break; } } // j = -1 means no element // is found in a[i] so // return 0 if (j == -1) return 0; } return sum; } // Driver Code static void Main() { int [,]arr = new int[,]{{1, 7, 3, 4}, {4, 2, 5, 1}, {9, 5, 1, 8}}; int n = arr.GetLength(0); Console.Write(maximumSum(arr, n)); } } // This code is contributed by // Manish Shaw (manishshaw1) ``` ## PHP ```php <?php // PHP program to find maximum // sum by selecting a element // from n arrays $M = 4; // To calculate maximum sum // by selecting element from // each array function maximumSum($a, $n) { global $M; // Sort each array for ($i = 0; $i < $n; $i++) sort($a[$i]); // Store maximum element // of last array $sum = $a[$n - 1][$M - 1]; $prev = $a[$n - 1][$M - 1]; $i; $j; // Selecting maximum element from // previoulsy selected element for ($i = $n - 2; $i >= 0; $i--) { for ($j = $M - 1; $j >= 0; $j--) { if ($a[$i][$j] < $prev) { $prev = $a[$i][$j]; $sum += $prev; break; } } // j = -1 means no element is // found in a[i] so return 0 if ($j == -1) return 0; } return $sum; } // Driver Code $arr = array(array(1, 7, 3, 4), array(4, 2, 5, 1), array(9, 5, 1, 8)); $n = sizeof($arr) ; echo maximumSum($arr, $n); // This code is contributed by m_kit ?> ``` **输出**： ``` 18 ``` 最坏情况下的时间复杂度：O（mn Log m）我们可以优化上述解决方案以在 O（mn）中工作。我们可以跳过排序以找到最大元素。 ## C++ ``` // CPP program to find maximum sum // by selecting a element from n arrays #include <bits/stdc++.h> #define M 4 using namespace std; // To calculate maximum sum by // selecting element from each array int maximumSum(int a[][M], int n) { // Store maximum element of last array int prev = *max_element(&a[n-1][0], &a[n-1][M-1] + 1); // Selecting maximum element from // previoulsy selected element int sum = prev; for (int i = n - 2; i >= 0; i--) { int max_smaller = INT_MIN; for (int j = M - 1; j >= 0; j--) { if (a[i][j] < prev && a[i][j] > max_smaller) max_smaller = a[i][j]; } // max_smaller equals to INT_MIN means // no element is found in a[i] so // return 0 if (max_smaller == INT_MIN) return 0; prev = max_smaller; sum += max_smaller; } return sum; } // Driver program to test maximumSum int main() { int arr[][M] = {{1, 7, 3, 4}, {4, 2, 5, 1}, {9, 5, 1, 8}}; int n = sizeof(arr) / sizeof(arr[0]); cout << maximumSum(arr, n); return 0; } ``` ## Python3 ```py # Python3 program to find maximum sum # by selecting a element from n arrays M = 4 # To calculate maximum sum by # selecting element from each array def maximumSum(a, n): # Store maximum element of last array prev = max(max(a)) # Selecting maximum element from # previoulsy selected element Sum = prev for i in range(n - 2, -1, -1): max_smaller = -10**9 for j in range(M - 1, -1, -1): if (a[i][j] < prev and a[i][j] > max_smaller): max_smaller = a[i][j] # max_smaller equals to INT_MIN means # no element is found in a[i] so # return 0 if (max_smaller == -10**9): return 0 prev = max_smaller Sum += max_smaller return Sum # Driver Code arr = [[1, 7, 3, 4], [4, 2, 5, 1], [9, 5, 1, 8]] n = len(arr) print(maximumSum(arr, n)) # This code is contributed by mohit kumar ``` **输出**： ``` 18 ``` **时间复杂度**： O（mn） * * * * * *