Recursive Definition
Recursive algorithms gain efficiency by reducing the scope of the problem until the solution is trivial. Thus, we need to define the problem in terms of sub-array. With that in mind, we can define longest-increasing subsection as the first array element plus the longest-increasing subsection of all remaining elements that are greater than that first array element.
In pseudo-code:
LIS(a) = a[0] + LIS(a[1:]>a[0])
Now that we have that definition, we need a terminal state. Since the last subarray in this definition will be an empty array, that is the terminal state. if(a == []): return 0
will be the end of the recursive chain.
Implementation Details
Since c does not have slices like Python, we can traverse with a pointer from the head of the remaining array. We use the address of the last element to flag the end of the traversal.
int _lis(int *arr, int *end){
if(arr == NULL || end == NULL) return 0; //input validation
//arr holds the last element of the lis, so we need a traversal pointer
int *traverse;
traverse = arr;
//Find the next array element greater than the current lis
while(*traverse <= *arr && traverse != end)
{ traverse++; }
if(traverse == end) //traversal reached end of the array
{
return (*traverse > *arr)? 1: 0; //Check if the last element is in the lis
}
return 1+_lis(traverse, end) //look at the rest of the list
}
Now you can re-write your input function LIS
to give a clean face to the user:
LIS(int arr[], int arr_len){
if(len == 0) return 0;
int max = 0, temp;
for(int i = 0; i < arr_len; ++i){
temp = _lis(&(arr[i]), &(arr[arr_len-1]));
max = (temp > max)?temp: max;
}
}
This way, you traverse the array at most once for each starting point. It's still O(n^2), but that's much better than O(n!) and it shows the recursive definition much more clearly.