Question

Given an array of integers, find the longest non-decreasing subsequences (the subsequence does

not need to be consecutive). For example, A = [8,5,2,10,3,6,9,7] contains the longest subsequences
[2,3,6,9] and [2,3,6,7].
(1) Explain how many non-consecutive subsequences are in an array of size n;
(2) Formulate the recursive relation of the optimal solution (do not miss the base case);
(3) Design a bottom-up (iterative) algorithm to calculate the length of the longest non-decreasing
subsequences (pseudo code);
(4) Analyze the complexity of your algorithm.

Answer 1

The number of non-consecutive subsequences in an array of size n can be found using combinatorics. The recursive relation for finding the length of the longest non-decreasing subsequence can be formulated as dp[i] = max(dp[j] + 1) for all j < i such that A[j] <= A[i]. The algorithm to calculate the length of the longest non-decreasing subsequences is a bottom-up approach with a time complexity of O(n^2).

Step-by-step explanation:

(1) The number of non-consecutive subsequences in an array of size n can be found using combinatorics. Since we are considering non-decreasing subsequences, the number of subsequences can be found using the formula 2^n - 1.

(2) The recursive relation for finding the length of the longest non-decreasing subsequence is as follows:
Let dp[i] be the length of the longest non-decreasing subsequence ending at index i in the array A. Then,
dp[i] = max(dp[j] + 1) for all j < i such that A[j] <= A[i].
The base case is dp[0] = 1, as the longest non-decreasing subsequence ending at index 0 is just A[0] itself.

(3) Here is the bottom-up algorithm in pseudo code:

dp = array of size n, initialized with 1
for i from 1 to n:
 for j from 0 to i-1:
if A[j] <= A[i]:
 dp[i] = max(dp[i], dp[j] + 1)
answer = maximum value in dp

(4) The time complexity of the algorithm is O(n^2) as we are looping through all possible pairs of indices. The space complexity is O(n) as we are using an extra array to store the lengths of the subsequences.