n个数组中的升序元素的最大和
原文： 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 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 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
# 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#
// 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 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
# 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)。
版权属于：月萌API www.moonapi.com，转载请注明出处
