This is essentially a variant of the longest increasing (or non-decreasing) subsequence problem. Here instead of a single array, we have the choice from two of them a[i] or b[i].
We will maintain two states for each i, dp[i][j] where 1 <= i <= n and j = {0, 1}.
Intuitively, dp[i][0] denotes the length of the longest subsequence when a[i] is present in the subsequence
Similarly, dp[i][1] denotes the length of the longest subsequence when b[i] is present in the subsequence
dp[i][0] = 1 + MAX { dp[k][0] if a[i] >= a[k] for all 1 <= k < i
dp[k][1] if a[i] >= b[k] for all 1 <= k < i
0 Otherwise }
dp[i][1] = 1 + MAX { dp[k][0] if b[i] >= a[k] for all 1 <= k < i
dp[k][1] if b[i] >= b[k] for all 1 <= k < i
0 Otherwise }
Answer will be the maximum over all dp[x][y] entries (1 <= x <= n and y = {0, 1})
Complexity Analysis:
Space: Ɵ(2*n) = Ɵ(n)
Time: Ɵ(n*n) = Ɵ(n2), Sum(2*(i-1)) for all 1 <= i <= n
Trivial exercise:
How to find out the maximum subsequence (not just the length)? What if more than one are of the maximum length?