Maximum Length of Chain

The basic idea of this approach is to break the original problem into sub-problems. Let us sort the array/list of pairs by the first integer in non-decreasing order and define a recursive function 

getLength(int i)

Which returns the length of the longest chain which ends at pairs[i]. As per given in the problem statement pair[i] can follow a pair[j] (for any integer ‘j’) if pairs[i][0] > pairs[j][1]. Since the array/list is sorted in nondecreasing order and also it is given that the second integer is always greater than the first integer in any pair, ‘j’ must be less than ‘i’. 

Therefore, we can define getLength(i) = max(getLength(i), getLength(j) + 1) if j < i and ( pairs[i][0] > pairs[j][1] ) holds true.

Now, consider the following steps to implement getLength(i) :

• If (i == 0) then return 1 because a single pair will make a chain of length one.
• Otherwise, initialize a variable “ans” to one which stores the length of the longest chain ending at pairs[i] start traversing the array/list using a variable ‘j’ such that ‘j’ < ‘i’
  • If pairs[i][0] > pairs[j][1] then update ans = max(ans, 1 + getLength(j) )
• Return “ans”.

O(2 ^ N), Where ‘N’ is the number of pairs in the given array/list.

Since we are using a recursive function which can be defined as f(n) = f(n - 1) + f(n - 2) + . . . + f(1) in the worst case. So the few steps of finding the complexity are below

First, look at the problem as :

	F(N) = a F(N - 1) + c So,
	F(1) = a * F(0) + c = a + c
	F(2) = a * F(1) + c = a*a + a * c + c
	F(3) = a * F(2) + c = a * a * a + a * a * c + a * c + c

Note that this creates a pattern. specifically:

    F(N) = sum(a ^ j c ^ (n - j), j = 0, ..., N)

Put c = 1 gives,

    F(N) = sum(a ^ j, j = 0, ..., N)

This is a geometric series, which evaluates to :

    F(N) = (1 - a ^ (N + 1)) / (1 - a)
         = (1 / (1 - a)) - (1 / (1 - a)) a ^ N
         = (1 / (a - 1))(-1 + a ^ (N + 1))
	For N >= 0.

Note that this formula is the same as given above for c=1 using the z-transform method. 

Again, O(a ^ N). Put a = 2 because our problem split into two sub-problems. So overall time complexity will be O(2 ^ N).

O(N), where ‘N’ is the number of pairs.

Since we are using a recursive function where there may be ‘N’ states present in the recursive call stack in the worst case. So the overall space complexity will be O(N).