Why do we use dynamic memory allocation in general and why did we use it in this particular example? Dynamic Programming C/C++ implementation of LIS(Longest Increasing Subsequence) problem

/* lis() returns the length of the longest increasing
subsequence in arr[] of size n */

int lis( int arr[], int n )
{
int *lis, i, j, max = 0;
lis = (int*) malloc ( sizeof( int ) * n );

/* Initialize LIS values for all indexes */
for (i = 0; i &lt; n; i++ )
    lis[i] = 1;

/* Compute optimized LIS values in bottom up manner */
for (i = 1; i &lt; n; i++ )
    for (j = 0; j &lt; i; j++ ) 
        if ( arr[i] &gt; arr[j] &amp;&amp; lis[i] &lt; lis[j] + 1)
            lis[i] = lis[j] + 1;

/* Pick maximum of all LIS values */
for (i = 0; i &lt; n; i++ )
    if (max &lt; lis[i])
        max = lis[i];

/* Free memory to avoid memory leak */
free(lis);
return max;
}


It is a code from www.geeksforgeeks.org . I have seen explanations that memory is allocated(when done dynamically) on heap,  which is a free store of (very large) memory, so it makes sense to only use dynamic allocation when memory required exceeds memory of stack used for storing variables and data locally allocated in functions.

Would it make a difference if I declared array as int arr[n] (as n is given by user in input) and then in main function use lis(arr, n) ? If so, why? If not, what else does dynamic allocation benefit from in this case and in general?
If you declared array as int arr[n] then the memory might be allocated on the Stack and arr would exist as long as the function lis exists, i.e., it would be allocated locally in the lis. malloc on the other hand, would allocate the memory on the Heap and the array would exist until you explicitly free it using free. Nevertheless, as Yuval Filmus noted, memory allocation for the variable length arrays depends on compiler implementation and environment (for example underlying environment may have no distinction between heap and stack). In addition, the GNU C Compiler allocates memory for variable length arrays on the stack.

However, regarding the time or space complexity of the algorithm, it would not make any difference. In particular, the time complexity of an algorithm has nothing to do with its implementation in a particular language.