Video of the week

This is a must-watch video about one of us trying to reach the stars :-)

Well done #HRejterzy

Maximum sub-square in NxM matrix (Not all 0,1)

My task was to find sub-squre (simple square inside given matrix) in NxM matrix where sum of elements is max.

Output: max, x-index, y-index of first sub-square element

matrix

and the solution is:

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. typedef struct
  5. {
  6. int value;
  7. int x;
  8. int y;
  9. } matrixElement;
  10.  
  11. int main()
  12. {
  13. int n = 3;
  14. int m = 4;
  15. matrixElement matrix[n][m];
  16. matrixElement matrixNew[n*m];
  17.  
  18. int z = 0;
  19. for(int i = 0; i<n; ++i)
  20. {
  21. for(int k=0; k<m; ++k)
  22. {
  23. // Put example values into the dwo-dim array (here I add indexes, You can do whatever).
  24. matrix[i][k].value = i + k;
  25. matrix[i][k].x = i;
  26. matrix[i][k].y = k;
  27. cout << matrix[i][k].value << " ";
  28. if(k == (m-1))
  29. {
  30. cout << "\n";
  31. }
  32.  
  33. // Rewrite values into one-dim array.
  34. matrixNew[z].value = matrix[i][k].value;
  35. matrixNew[z].x = matrix[i][k].x;
  36. matrixNew[z].y = matrix[i][k].y;
  37. ++z;
  38. }
  39. }
  40.  
  41. /*
  42. cout << "\n";
  43. for(int zz = 0; zz<n*m; ++zz)
  44. {
  45. cout << matrixNew[zz].value << " ";
  46. }
  47. cout << "\n";
  48. cout << "\n";
  49. */
  50.  
  51. int max = -1;
  52. int xx = -1;
  53. int yy = -1;
  54. for(int ii=0; ii<(n*m)-m-1; ++ii)
  55. {
  56. if(matrixNew[ii].y == (m-1))
  57. continue;
  58.  
  59. // Use relations between values:
  60. // second element is +1 from the first one
  61. // third element of square is +m elements away from the first one
  62. // fourth is +m+1 from the first one
  63. if(matrixNew[ii].value + matrixNew[ii+1].value + matrixNew[ii+m].value + matrixNew[ii+m+1].value > max)
  64. {
  65. max = matrixNew[ii].value + matrixNew[ii+1].value + matrixNew[ii+m].value + matrixNew[ii+m+1].value;
  66. xx = matrixNew[ii].x;
  67. yy = matrixNew[ii].y;
  68. }
  69. }
  70.  
  71. // Correct answer:
  72. cout << max << " " << xx << " " << yy << endl;
  73.  
  74. cin.get();
  75. return 0;
  76. }

1. It depends on You how to fill the matrix with values - I decided to add i, k indexes. You can do whatever, use random values or seconds or (..)

2. Every sub-square is created from four values in particular distance-configuration - first, first+1, first+m, first+1+m

3. You must remember that when You reach right boundary value - You skip creating sub-square because You cannot create one, for example from values: 3,4 (first row) and 1,2 (second row)

4. Count of steps related to creating sub-squares depends on particular condition, which is: for(int ii=0; ii<(n*m)-m-1; ++ii) - You cannot create sub-squares after You stop dealing with second-to-last row

5. You know how to find maximum value in one-dim array - so the rest is easy

The Key : change two-dim array into one-dim array (it is always better to deal with much simpler structure)