# 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） * * * * * *