도움이 되었습니까?

문제


In this tutorial, we will be discussing a program to find maximum sum of increasing order elements from n arrays.

For this we will be provided with N arrays of M size. Our task is to find the maximum sum by selecting one element from each array such that element from the previous array is smaller than the next one.

Example

 Live Demo

#include <bits/stdc++.h>
#define M 4
using namespace std;
//calculating maximum sum by selecting
//one element
int maximumSum(int a[][M], int n) {
   for (int i = 0; i < n; i++)
      sort(a[i], a[i] + M);
   int sum = a[n - 1][M - 1];
   int prev = a[n - 1][M - 1];
   int i, j;
   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;
         }
      }
      if (j == -1)
         return 0;
   }
   return sum;
}
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;
}

Output

18
raja
Published on 09-Sep-2020 13:05:50

도움이 되었습니까?
제휴하지 않습니다 Tutorialspoint
scroll top