Answer to Question #100129 in C++ for DeadBeast

Question

3. Create a class node that contains a random value -50<x<50, Create a 2-d array (size m, n entered by the user ) of these random nodes find the internal square with the largest sum of values within it. For example if the user enters m = 4, and n=3 and values are generated it might look like this

-32 4 -16 8
-2 5 -22 11
5 -10 3 12
33 5 -17 -33

You might think the maximum sub-matrix would be
-2 5
5 -20
33 5 sum =26

But it is actually
8
11
12 sum =31 you need to check all possible rectangles, this is a 2d version of
the greatest common substring problem.

Answer 1

#include <iostream>
#include <vector>
#include <iomanip>
#include <cstdlib>
using namespace std;


class Node
{
public:
	int value;
	Node()
	{
		value = rand() % 101 - 50;
	}
};


vector<vector<Node>> a;


bool subMatrixSum(int i0, int j0, int n0, int m0, int& sum, int nMat, int mMat)
{
	if (i0 + n0 > nMat || j0 + m0 > mMat) 
		return false;


	sum = 0;
	for (int i = i0; i < i0 + n0; i++)
		for (int j = j0; j < j0 + m0; j++)
			sum += a[i][j].value;


	return true;
}


void printSubmatrix(int i0, int j0, int n, int m)
{
	for (int i = i0; i < i0 + n; i++)
	{
		for (int j = j0; j < j0 + m; j++)
			cout << setw(3) << a[i][j].value << ' ';
		cout << '\n';
	}
}


int main()
{
	srand(time(NULL));
	int nMat, mMat;
	cin >> nMat >> mMat;
	for (int i = 0; i < nMat; i++)
	{
		vector<Node> temp;
		for (int j = 0; j < mMat; j++)
		{
			temp.push_back(Node());
			cout << temp[j].value << " ";
		}
		a.push_back(temp);
		cout << "\n";
	}


	int iMax = 0, jMax = 0, nMax = 1, mMax = 1;
	int sMax = a[0][0].value;


	for (int n = 1; n <= nMat; n++)
		for (int m = 1; m <= mMat; m++)
			for (int i = 0; i < nMat; i++)
				for (int j = 0; j < mMat; j++)
				{
					int s;
					bool fit = subMatrixSum(i, j, n, m, s, nMat, mMat);
					if (fit && s > sMax)
					{
						iMax = i;
						jMax = j;
						nMax = n;
						mMax = m;
						sMax = s;
					}
				}


	cout << "Element sum: " << sMax << endl;
	cout << "\nSubmatrix:\n";
	printSubmatrix(iMax, jMax, nMax, mMax);
}