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 < n; i++ )
    lis[i] = 1;

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

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

/* Free memory to avoid memory leak */
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?

  • 1
    $\begingroup$ In general, dynamic memory allocation is used either when we don't know at compile time how much will be needed, or when the required lifespan of items in the memory doesn't correspond well to entering and leaving blocks of code. The specifics of any C/C++ program is off-topic, here, since we don't deal with programming questions. $\endgroup$ – David Richerby Aug 12 '17 at 12:36
  • 1
    $\begingroup$ This seems to be a question about how declarations like int arr[n] are implemented in C/C++, and so off-topic here. $\endgroup$ – Yuval Filmus Aug 12 '17 at 13:47

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.

| cite | improve this answer | |
  • 3
    $\begingroup$ According to Wikipedia, stack allocation is implementation dependent – VLAs could conceivably be allocated on the heap. (Perhaps Wikipedia is ignoring the C99 standard here.) $\endgroup$ – Yuval Filmus Aug 12 '17 at 13:46

Not the answer you're looking for? Browse other questions tagged or ask your own question.