How to analysis the complexity of this LIS program?
The worst case running time of your first procedure satisfies the recurrence
$$
T(n) = T(n-1) + \cdots + T(1) + O(1).
$$
The worst case running time of your second procedure is $T(n) + \cdots + T(1) + O(1)$, which we can identify with $T(n+1)$. Thus it suffices to understand the first recurrence.
Let us assume replace $O(1)$ with $1$, obtaining the recurrence
$$
T(n) = T(n-1) + \cdots + T(1) + 1.
$$
Therefore
$$
T(n+1) = T(n) + [T(n-1) + \cdots + T(1) + 1] = 2T(n).
$$
Consequently, $T(n) = 2^{n-1} T(1) = 2^{n-1}$.
If we replace $1$ back with $O(1)$, we get $T(n) = O(2^n)$.