Maximum sum of hourglass in an array I am solving some questions on HackerRank for practice purposes. This morning I solved one called Maximum sum of hourglass in an array.

Given an array:

1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0


the hourglass sum is 7 and we need to find the maximum sum of all hourglass in an array.

My implementation:

#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;climits&gt;

using std::vector;

int hourglassSum(vector&lt;vector&lt;int&gt;&gt; &amp;arr) {
    int highestSum = INT_MIN;
    for (size_t i = 1; i &lt; arr.size() - 1; ++i) {
        int sum = 0;
        for (size_t j = 1; j &lt; arr.at(i).size() - 1; ++j) {
            sum = arr.at(i - 1).at(j - 1) +
                  arr.at(i - 1).at(j) +
                  arr.at(i - 1).at(j + 1) +
                  arr.at(i).at(j) +
                  arr.at(i + 1).at(j - 1) +
                  arr.at(i + 1).at(j) +
                  arr.at(i + 1).at(j + 1);
            if (sum &gt; highestSum) {
                highestSum = sum;
            }
        }
    }
    return highestSum;
}

int main() {
    vector&lt;vector&lt;int&gt;&gt; nums = 
        {{1, 1, 1, 0, 0, 0}, // 0
         {0, 1, 0, 0, 0, 0}, // 1
         {1, 1, 1, 0, 0, 0}, // 2
         {0, 0, 2, 4, 4, 0}, // 3
         {0, 0, 0, 2, 0, 0}, // 4
         {0, 0, 1, 2, 4, 0}}; // 5
    vector&lt;vector&lt;int&gt;&gt; nums2 = 
        {{0, -4, -6, 0, -7, -6},
         {-1, -2, -6, -8, -3, -1},
         {-8, -4, -2, -8, -8, -6},
         {-3, -1, -2, -5, -7, -4},
         {-3, -5, -3, -6, -6, -6},
         {-3, -6, 0, -8, -6, -7}};
    std::cout &lt;&lt; hourglassSum(nums) &lt;&lt; std::endl;  // expected 19
    std::cout &lt;&lt; hourglassSum(nums2) &lt;&lt; std::endl;  // expected -19
}


My questions:


I think the runtime of this code is O(n*m), does anyone think there is a better way of doing this?
Does the code look efficient and readable?


Thanks
Readability

The vector initialization in main would be more readable if the {{ and }} were broken out onto separate lines.

    vector&lt;vector&lt;int&gt;&gt; nums = {
        {1, 1, 1, 0, 0, 0}, // 0
        {0, 1, 0, 0, 0, 0}, // 1
        {1, 1, 1, 0, 0, 0}, // 2
        {0, 0, 2, 4, 4, 0}, // 3
        {0, 0, 0, 2, 0, 0}, // 4
        {0, 0, 1, 2, 4, 0}
    }; // 5
    vector&lt;vector&lt;int&gt;&gt; nums2 =
    {
         {0, -4, -6, 0, -7, -6},
         {-1, -2, -6, -8, -3, -1},
         {-8, -4, -2, -8, -8, -6},
         {-3, -1, -2, -5, -7, -4},
         {-3, -5, -3, -6, -6, -6},
         {-3, -6, 0, -8, -6, -7}
    };


Complexity

The function int hourglassSum(vector&lt;vector&lt;int&gt;&gt; &amp;arr) is too complex (does too much) it would be better if it was 2 functions:

int singleHourglassSum(vector&lt;vector&lt;int&gt;&gt; &amp;arr, size_t i, size_t j)
{
    int hourglassSum =
            arr.at(i - 1).at(j - 1) +
            arr.at(i - 1).at(j) +
            arr.at(i - 1).at(j + 1) +
            arr.at(i).at(j) +
            arr.at(i + 1).at(j - 1) +
            arr.at(i + 1).at(j) +
            arr.at(i + 1).at(j + 1);

    return  hourglassSum;
}

int maxHourglassSum(vector&lt;vector&lt;int&gt;&gt; &amp;arr) {
    int highestSum = INT_MIN;
    for (size_t i = 1; i &lt; arr.size() - 1; ++i) {
        int sum = 0;
        for (size_t j = 1; j &lt; arr.at(i).size() - 1; ++j) {
            sum = singleHourglassSum(arr, i, j);
            if (sum &gt; highestSum) {
                highestSum = sum;
            }
        }
    }
    return highestSum;
}


Keep in mind the Single Responsibility Principle:

The Single Responsibility Principle states:


  that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.