A parity alternating sequence is a sequence of integers such…

A parity alternating sequence is a sequence of integers such that the parity of consecutive terms is different. That is, a sequence is parity alternating if it is of the form even, odd, even, odd, even, odd… or odd, even, odd, even, odd…  Given a sequence of integers, design a Dynamic Programming Algorithm to find the length of the longest increasing subsequence that is parity alternating. Additionally, you are given a parity function such that parity(x) will return even or odd in O(1). Example: Given A=, your output should be 3, corresponding to the length of . Note that is also increasing, but it is not parity alternating. Please answer the following parts:  1. Define the entries of your table in words. E.g. T(i) or T(i, j) is …2. State a recurrence for the entries of your table in terms of smaller subproblems. Don’t forget your base case(s).