C++プログラムのn個の配列からの昇順要素の最大合計

この問題では、サイズnXmの2次元行列が与えられます。私たちのタスクは、n個の配列から増加する次数要素の最大合計を見つけるプログラムを作成することです。

プログラムの説明 −ここでは、i番目の行の要素が（i + 1）番目の行の要素よりも小さくなるように、各行から1つの要素を取得して、要素の最大合計を見つける必要があります。等々。そのような合計が不可能な場合は、結果が不可能であることを示す-1を返します。

問題を理解するために例を見てみましょう

入力

mat[][] = {
   {4, 5, 1, 3, 6},
   {5, 9, 2, 7, 12},
   {13, 1, 3, 6, 8},
   {10, 5, 7, 2, 4}
}

出力

31

説明

Taking elements from the matrix to create max Sum:
6 + 7 + 8 + 10 = 31,
6 From array 1, the maximum value.
7 from array 2, choosing 12(maximum value) cannot provide a solution.
8 from array 3, choosing 13(maximum value) cannot provide a solution.
10 From array 4, the maximum value

ソリューションアプローチ

この問題の解決策は、配列の配列の最後の配列から要素を選択してから、指定された要素よりも小さい可能な最大の要素を選択することです。

ここで、このソリューションを使用すると、（i + 1）番目の配列（行）の要素よりも小さい要素がitharray（行）にない場合が1つあります。ここでは、-1を返します。

配列を並べ替えることは、ソリューションの効率を高めるのに役立ちます。昇順でソートするかのように、最大​​の要素はインデックスm-1にあり、次の要素は小さくなります。したがって、条件を満たす最大の要素を見つけるのは簡単です。

アルゴリズム

maxSum =0、currMax

ステップ1 −

Sort each array of the array of arrays (each will have elements in
increasing order).

ステップ2 −

currMax = mat[n−1][m−1], the last element or the last row. Update
maxSum, maxSum = currMax.

ステップ3 −

行列の行をループします。i=n-2から0です。

ステップ3.1 −

Find the max element in mat[i][] which is smaller than
currMax at index j.

ステップ3.2 −

if j < 0, i.e. no value found. Return −1.

ステップ3.3 −

Update currMax. currMax = mat[i][j].

ステップ3.4 −

Update maxSum, maxSum = currMax.

ステップ4 −

Return maxSum.

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
#define M 5
using namespace std;
int calcMaxSumMat(int mat[][M], int n) {
   for (int i = 0; i < n; i++)
   sort(mat[i], mat[i] + M);
   int maxSum = mat[n − 1][M − 1];
   int currMax = mat[n − 1][M − 1];
   int j;
   for (int i = n − 2; i >= 0; i−−) {
      for (j = M − 1; j >= 0; j−−) {
         if (mat[i][j] < currMax) {
            currMax = mat[i][j];
            maxSum += currMax;
            break;
         }
      }
      if (j == −1)
      return 0;
   }
   return maxSum;
}
int main() {
   int mat[][M] = {
      {4, 5, 1, 3, 6},
      {5, 9, 2, 7, 12},
      {12, 1, 3, 6, 8},
      {10, 5, 7, 2, 4}
   };
   int n = sizeof(mat) / sizeof(mat[0]);
   cout<<"The maximum sum of increasing order elements from n arrays is "<<calcMaxSumMat(mat, n);
   return 0;
}

出力

The maximum sum of increasing order elements from n arrays is 31