Computing sum on column + sum on row + sum on each diagonal I have the following problem:
I read from a file the dimension(n) of the matrix(which is n * n) and the matrix.
For each element in the matrix I have to compute sum of row + sum of column + sum of the diagonal which the element is on and is parallel to main diagonal + sum of the diagonal which the element is on and is parallel to antidiagonal, and find the element with max corresponding sum and coordinates(row and column) on which the element is found. Element itself should be taken into count just once.

I have a working program, but I need it to be faster. How could I solve this problem faster? Can my algorithm be improved or I have to write another one? 2 ≤ n ≤ 300, -10000 ≤ m[i][j] ≤ 10000

Input file:

3
 1  -8  3
-2   4  5
 6  -9  7


Output file:

18
0 2


Code:

#include &lt;set&gt;  
#include &lt;iostream&gt;
#include &lt;fstream&gt;
#include &lt;limits&gt;

using namespace std;
int sumOnRow(int row, int n, int **m)
{
    int i;
    int sum = 0;
    for (i = 0; i &lt; n; i++)
        sum += m[row][i];
    return sum;
}

int sumOnColumn(int column, int n, int **m)
{
    int i;
    int sum = 0;
    for (i = 0; i &lt; n; i++)
    {
        sum += m[i][column];
    }
    return sum;
}

int sumOnAD(int i, int j, int n, int **m)
{
    int a = i - 1;
    int b = j + 1;
    int sum = 0;
    while ((a &gt;= 0) &amp;&amp; (b &lt; n))
    {
        sum += m[a--][b++];
    }
    a = i + 1;
    b = j - 1;
    while ((a &lt; n) &amp;&amp; (b &gt;= 0))
    {
        sum += m[a++][b--];
    }
    return sum;
}

int sumOnMD(int i, int j, int n, int **m)
{
    int a = i + 1;
    int b = j + 1;
    int sum = 0;
    while ((b &lt; n) &amp;&amp; (a &lt; n))
    {
        sum += m[a++][b++];
    }
    a = i - 1;
    b = j - 1;
    while ((a &gt;= 0) &amp;&amp; (b &gt;= 0))
    {
        sum += m[a--][b--];
    }
    return sum;
}

int main()
{
    fstream in;
    in.open ("inputFile.in");
    if (!in)
    {
        cerr &lt;&lt; "Can't open input file\n";
    }
    fstream out;
    out.open ("outputFile.out", ios::out);
    if (!out)
    {
        cerr &lt;&lt; "Can't open output file\n";
    }

    short n;
    in &gt;&gt; n;

    int i;
    int **m = new int *[n];
    for (i = 0; i &lt; n; i++)
        m[i] = new int [n];

    int j;
    //read the matrix
    for (i = 0; i &lt; n; i++)
    {
        for (j = 0; j &lt; n; j++)
        {
            in &gt;&gt; m[i][j];
        }
    }

    int elementSum = 0;
    int maxSum = INT_MIN;
    int savedI = 0;
    int savedJ = 0;

    for (i = 0; i &lt; n; i++)
    {
        for (j = 0; j &lt; n; j++)
        {
            elementSum += sumOnRow(i, n, m);
            elementSum += sumOnColumn(j, n, m);
            elementSum += sumOnMD(i, j, n, m);
            elementSum += sumOnAD(i, j, n, m);
            //element was taken into count both in the sum on row and the sum on column
            elementSum -= m[i][j];
            if (elementSum &gt; maxSum)
            {
                maxSum = elementSum;
                savedI = i;
                savedJ = j;
            }
            elementSum = 0;
        }
    }
    out &lt;&lt; maxSum &lt;&lt; "\n" &lt;&lt; savedI &lt;&lt; " " &lt;&lt; savedJ;
    return 0;
    }
For every element, you currently sum \$n\$ elements for the row, column, diagonal and anti-diagonal, so \$4*n\$ elements.
That's a total of \$4*n^3\$ adds.

That can be improved on easily by pre-processing:


Build an array of the sums for all rows, columns, diagonals and anti-diagonals. You need \$4*n\$ space and \$4*n^2\$ adds.
Add the proper sums for each element, that's \$4\$ adds per element, for a total of \$4*n^2\$ adds.
Together, that's \$8*n^2\$ adds.


In conclusion, you can trade \$4*n\$ extra space for a speed-up by a factor of \$n/2\$.

Regarding your current code:


I cannot find anyplace you use something from &lt;set&gt;. So, why include it?
You should avoid using namespace std; It's a plague and just biding its time to bite you later.
Why is “using namespace std;” considered bad practice?

You can import selected identifiers with using std::cout;, and qualify others with std::cin.
You know you can introduce a variable in the initializer-part of the for-loop?
There's no need for a separate step to open a fstream. User the right ctor.
You noticed an error, you wrote to stderr about it, so why do you try to muddle on instead of aborting?
You never check whether input failed. Are you completely sure the input is well-formed?
Consider merging your allocations where possible. new and delete are quite costly after all.
return 0; is implicit in main().
You never free the memory you allocated. That's actually a good thing as cleaning up just for the OS to take everything down is wasted effort. Beware false positives in leak-detectors though.
I suggest a comment // m and m[0] to m[n - 1] intentionally left allocated though, in case anyone (else) later pokes around and might conceivably adopt it into a greater whole. Also shows you considered it.
You might consider investing into a class for square matrices. It's quite easy to build one.