In based on all the sums, what is the greatest sum of numbers in all the 5x5 sub

Question

In based on all the sums, what is the greatest sum of numbers in all the 5x5 submatrices after calculating.

A PR researcher have collected stinkbugs population in a 2.5 x 2.5 km square field. In an effort of the United States Department of Agriculture who has been working to understand the threat stinkbugs pose and detect patterns in how they move. Top down the problem, and find the sum of bugs in a n x n small area (say n-5) which may signal their movement behavior in a larger area. In the 25x25 grid below, twenty five neighboring numbers have been marked in blue in a 5x5 matrix. They represent number of bugs found in smaller area: 30 35 35 25 34 50 92 54 46 57 69 71 9 5 5 79 70 60 66 91 54 76 13 84 95 96 5 14 38 81 38 72 40 81 48 1 13 45 57 55 11 85 70 30 60 25 5 25 81 56 89 70 84 43 53 6 74 11 94 26 37 44 66 74 70 16 77 38 53 70 4 72 88 84 56 19 98 33 82 52 35 40 72 8 57 89 50 82 32 48 35 20 72 0 74 23 69 19 37 17 0 16 27 82 77 23 24 61 70 87 32 53 78 49 61 84 98 88 87 38 36 45 12 38 51 70 11 1 45 12 20 52 78 23 6 59 85 71 22 21 58 9 6 40 25 63 58 54 85 54 86 90 79 38 62 81 22 56 39 44 29 67 47 93 64 58 64 14 30 4 98 34 31 46 16 12 48 49 92 34 39 83 80 27 8 12 80 70 48 38 92 21 85 94 47 21 17 38 56 49 4 84 53 73 33 5 66 57 82 56 38 53 95 53 10 57 24 42 46 64 75 40 78 69 53 59 80 86 73 57 37 81 93 99 53 81 95 50 22 37 1 34 41 28 28 88 91 83 95 20 60 18 72 94 86 77 79 86 64 76 97 7 30 9 26 80 20 95 8 51 47 22 67 54 62 51 24 66 50 20 16 46 50 70 23 85 54 78 6 24 60 50 74 58 24 16 36 41 63 3 1 5 18 78 67 90 31 78 92 58 8 28 23 81 62 48 94 97 15 29 80 32 64 57 32 68 60 54 45 89 32 68 47 68 45 33 48 23 76 52 27 39 23 7 64 47 8 21 92 53 94 77 95 84 20 33 98 82 56 85 23 68 46 19 41 26 58 10 57 88 12 51 61 86 32 86 51 59 39 30 20 76 32 38 65 31 21 61 89 22 48 60 38 28 85 87 82 67 17 60 11 3 80 73 49 76 82 97 63 35 97 60 61 68 85 23 71 50 36 21 63 90 60 18 36 35 98 97 97 88 7 70 28 36 34 54 32 12 65 85 5 40 56 72 40 10 72 34 24 13 24 50 88 52 50 94 59 7 40 25 74 87 12 98 28 17 85 97 85 88 90 38 36 74 90 55 33 21.43 27 16 75 74 37 94 83 13 28 3 61 26 91 49 34 25 3 30 17 20 63 61 17 3 21 53 28 49 82 46 30 17 10 73 42 77 20 74 40 95 96 4 68 79 97 65 30 62 45 32 57 68 86 91 50 16 89 95 41 49 95 60 28 99 94 61 98 87 49 70 67 79 57 1 11 41 14 7 32 90 36 10 15 82 58 91 82 79 26 20 16 68 92 35 17 74 79 74 47 37 1 51 96 80 20 73 74 15 93 8 38 80 14 66 76 82 37 8 77 85 83 77 15 94 33 70 71 10 53 34 70 72 15 40 65 16 79 50 95 61 65 50 48 23 90 51 2

Explanation / Answer

int largestZigZagSumRec(int mat[][MAX], int i,

                                int j, int n)

{

   if (dp[i][j] != -1)

      return dp[i][j];

   // If we have reached bottom

   if (i == n-1)

     return (dp[i][j] = mat[i][j]);

   // Find the largest sum by considering all

   // possible next elements in sequence.

   int zzs = 0;

   for (int k=0; k<n; k++)

     if (k != j)

       zzs = max(zzs, largestZigZagSumRec(mat, i+1, k, n));

   return (dp[i][j] = (zzs + mat[i][j]));

}

// Returns largest possible sum of a Zizag sequence

// starting from top and ending at bottom.

int largestZigZag(int mat[][MAX], int n)

{

   memset(dp, -1, sizeof(dp));

   // Consider all cells of top row as starting point

   int res = 0;

   for (int j=0; j<n; j++)

     res = max(res, largestZigZagSumRec(mat, 0, j, n));

   return res;

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.