Question

I need to write a c/c++ code to find the maximum sum in those possible combinations of arrays.

There are N arrays with S elements.

ex2: 4 arrays with 3 elements.We want to find the greater number in the same column of two arrays(may possible be three or four...arrays), and sum those greater number to find the greatest sum in all of the combinations in those 4 arrays, like:

A: [50, 60, 70]

B: [80, 40, 20]

C: [30, 100, 50]

D: [75, 95, 40]

A+B = 80+60+70=210

A+C= 50+100+70=220

A+D= 75+95+70=240

B+C=80+100+50=230

B+D=80+95+40=215

C+D=75+100+50=225

240 is the greatest.

so 240 is the answer.

Is there any smart solution?

(I only have an idea about iterate all arrays to calculate all possible sum and then find the maximum.)

No brutal iteration solution.

Answer 1

Here we use simple logic to tackle the problem when we study the scenario, the correct requirement for the question is to find the 2 arrays which will yield the highest possible sum(maximum sum in each column of the selected 2 array). by analyzing the problem we can easily understand that the highest possible sum from the selection of largest numbers in each row will be yielded by the pair of the array which has the highest sum of all its elements.

lets take the above question now :

the sum of the elements in each of the given arrays are

A {50,60,70} = 180

B{80,40,20} = 140

C{30,100,50} = 180

D{75,95,40} = 210

from above findings abviously array D will be selected but the second largest sum is here yielded by 2 arrays (A and C) so how to select the second array ? lets find out !!

while going through the question we find that we need largest of the number in each column so we come to the conclusion that we need the 'largest' number, I think now you got the thing! yes!! we need the array having larger elements. now this will be our second condition to choose

Now we can conclude that among 2 arrays A and D, array A has larger elements(A {50,60,70},C{30,100,50} = 180)

thus we get the 2 arrays without iterating every array for every element

array A {50,60,70} = 180 and D{75,95,40} = 210 will be arrays and the sum will be 75+95+70 = 240

here is the complete c++ program for reference

#include <iostream>

using namespace std;

//function to find sumof elements in the array

int sum(int arr[], int n) {
int sum = 0; // initialize sum

// Iterate through all elements
// and add them to sum
for (int i = 0; i < n; i++)
sum += arr[i];

return sum;
}

// function to find the final sum of two selected array
int maxSum(int arr1[], int arr2[], int n) {
int sum = 0;
for (int i = 0; i < n; i++) {

//comparing which array have the largest element
if (arr1[i] > arr2[i]) {
sum += arr1[i];
} else {
sum += arr2[i];
}
}
return sum;
}

//function to find which array contain huge number of larger elements

//this function returns a boolean value for checking in main function
bool largeElements(int arr1[], int arr2[], int n) {

//initialising the count
int l1 = 0;
int l2 = 0;
for (int i = 0; i < n; i++) {

//increase the corresponding count associated to the array
if (arr1[i] < arr2[i]) {
l2++;
}
if (arr1[i] > arr2[i]) {
l1++;
}
if (arr1[i] == arr2[i]) {
l1++;
l2++;
}
}

//returning true/false according to the count we obtained
if (l1 > l2 || l1 == l2) {
return true;
} else {
return false;
}
}
int main() {

//initializing the 2 dimensional array
int arr[4][3] = {
{
50,
60,
70,
},
{
80,
40,
20,
},
{
30,
100,
50,
},
{
75,
95,
40
}
};

//here n is total number of arrays inside the 2 dimensional array we declared

int n = sizeof(arr[0]) / sizeof(arr[0][0]);

//'total' is the number of elements in each of the array
int total = sizeof(arr) / sizeof(arr[0]);

//a is variable which hold the index of 2nd largest array and b will hold the largest array in the input.

// first we assume '0' is largest and '1' is second largest
int a = 1;
int b = 0;

// we verify with the 'if' constraint
if (sum(arr[0], n) < sum(arr[1], n)) {
a = 0;
b = 1;
}

//here we take each array to find the sum of elements in array and find the 2 largest arrays
for (int i = 2; i < total; i++) {
if (sum(arr[a], n) < sum(arr[i], n)) {
a = i;
}
if (sum(arr[a], n) == sum(arr[i], n)) {

//if the sum in array is found to be same we pass them to largeElement function to find the array which having the highest //number of larger number
if (largeElements(arr[i], arr[a], n)) {
a = i;
}
}

//if the next array is larger than the highest array
if (sum(arr[b], n) < sum(arr[i], n)) {
a = b;
b = i;
}

//if the sum in array is found to be same we pass them to largeElement function to find the array which having the highest //number of larger number

if (sum(arr[b], n) == sum(arr[i], n)) {
if (largeElements(arr[i], arr[b], n)) {
b = i;
}
}
}

//print the answer

cout << "sum is " << maxSum(arr[a], arr[b], n) << "\n";
cout << "array indexes are " <<a <<" and "<< b << "\n";
return 0;
}