please avoid them and focus on the problem here.
The problem is my time complexity to traverse is going too high.
No, your variable naming and abuse of C++ features is also a problem. For the most part your code is structured OK. It's moderately understandable, but fixing those things could make it really easily understandable. You do need to think about these things, not just so others can read your code, but so your future self can understand it, too.
Your variable names are not clear at all. I'm all for 1-letter variable names for loop control variables like
j. But you've gone too far for anyone who wants to understand your code. It's not hard to change
numMatrixes or if you really need short names,
numMats. (Also, you didn't really describe that there was more than one matrix in your description. Did I understand that correctly?)
m should be
Your actual matrixes should have better names, too.
a should be
maxi is better than your other names.
ma should be
counti is also ambiguous. What is it counting? It looks to me like it's counting the number of values that match the maximum value, so maybe call it
This code is very dense and difficult for a human to parse. I recommend using far more whitespace in your code. For example, I'd put spaces before and after every operator. That means
Also, you should add some empty lines between blocks of functionality from time to time. For example, between the
for loops, the
, andwhile loops. Even better would be to…
I see 3 things happening in the outer
while loop. You're:
- Reading in the input values for the array (while finding the maximum element)
- Replacing each element in the array with the maximum of its neighbors
- Finding the number of times you need to do that until you've filled the array with the maximum values
Each of those things should be a separate function.
continue keyword is essentially a
goto. As such, it can make code flow harder to understand than it needs to be. I don't think your use of it adds anything, so I'd remove it in favor of using
else clauses in your
ifs. For example in the first inner loop, I'd change it to look like this:
if(i == 0 || j == 0 || i == n + 1 || j == m + 1)
a[i][j] = 0;
cin >> a[i][j];
flag[i][j] = 0;
if(a[i][j] > ma)
ma = a[i][j];
It does the exact same thing, but is much clearer. Now I don't have to think, "does the continue apply to the inner or outer loop?" I just automatically understand what happens when the code runs.
I'd do the same thing with the other
Avoid magic numbers
You have a couple of uses of the number 8. What does it represent? Does it need to change if you change anything else in the code? It appears that you're trying to use the number of values in the
myints array. If that's what you want, you should use that directly. You can write it as:
const int numMyInts = sizeof(myints) / sizeof(myints);
Stop Abusing C++
You say you know that
using namespace std is bad, but you do it anyway. My compiler can't even find
bits/stdc++.h, so I had to include the 2 headers you actually need:
Errors and Warnings
My compiler (llvm) won't actually compile your code. It points out the error you have in the
myints array. It's only big enough to hold
ints, but you're trying to copy
long ints into it. This might work for small values, but not for values that exceed the size of
You have an unused variable
k. You should remove it.
Your algorithm fails for negative values.
In order to understand what's causing your code to be slow, you should profile it. That will tell you for certain where the slowdown is. You will often be surprised by the answer.
My first guess (and it's best to test it rather than guessing, because guesses are often wrong) is that it's costing you a lot of time copying the neighboring elements into the
myints array. I wonder if you could avoid the copies by using some pointer arithmetic? Finding the max of several values is simple enough that you probably don't need to call
max_elements(). You could manually unroll the loop into something like this:
const long int kRowStride = numCols - 2; // Number of elements to skip to get to the right element in the next row
long int *nextInt = &a[ i - 1 ][ j - 1 ];
long int currentMax = *nextInt;
currentMax = std::max(currentMax, *nextInt);
currentMax = std::max(currentMax, *nextInt);
nextInt += kRowStride;
//… etc.for the remaining 2 rows
It's possible that there's some matrix operation that will do the equivalent of your search in fewer steps. I don't remember enough matrix math to know off the top of my head whether that's true or not, but often the best optimization is not to optimize your algorithm, but to find a better algorithm. So I'd explore that route, as well.