I am a newbie who has been trying to improve at competitive programming and algorithmic thinking. Solving some problems and looking at several people's codes, I noticed a weird contrast between my habit and that of others.
In quite a bit of problems, we usually need to take an array (or whatever other data structure) of elements, and most of the time the number of elements is given first. Actually, what I am used to doing is
int n;
cin>>n;
int a[n];
On the other hand, I saw some people doing
int n;
int a[some_limit];
where some_limit is often the limit of n in all test cases as given in the problem description.
I wonder what kind of differences lie between those two approaches. Can they be interchangeably used and have almost the same time and space complexity? Are they equivalent as long as we ignore the difference between the time and space complexities?
The difference between these two approaches is that the second one declares the array at most how much you want, and the first one declares exactly how much you want. Sometimes, it may happen that it is given that "$$$N, T \le 10^5$$$ and the sum of $$$N$$$ over all testcases is $$$\le 10^5$$$", so in that case, if you declare an array of size $$$10^5$$$ for all testcases, you will get MLE. To avoid that, you can either use the first approach, or you can declare the array globally of size $$$10^5$$$ and then after each testcase, clear the memory that you used for that testcase.
Personally, I use the first approach, but you can use whichever one you are used to.
The first code make use of variable-length arrays which is not part of the c++ standard. However it is part of the C standard so turns out g++ will also accept the first piece of code.
If you're curious why this is the case (that c++ doesn't include variable length array in standard), you can search for "variable length arrays c++" for reasons. Essentially this makes the type of the array no longer known at compile time and doesn't work well with other features in c++.
Another reason is that you can't place the array as a global variable in the first approach (as the length has to be known when you declare the array) where you can in the second approach. This can be very convenient when you use functions.