Given an array arr of size N, the task is to make strictly increasing and strictly decreasing subsequences from the array such that each array element belongs to increasing subsequence or decreasing subsequence, but not both, or can be part of none of the subsequence. Minimize the number of elements that are not part of any of the subsequences and find the count of such elements.
Example 1:
Input: N = 12, arr[] = {7, 8, 1, 2, 4,
                 6, 3, 5, 2, 1, 8, 7}
Output: 2
Explanation: 
Increasing sequence can be :
           {1, 2, 4, 5, 8}.
Decreasing sequence can be :
           {7, 6, 3, 2, 1}.
So, only 2 (8, 7) elements are left 
which are not part of either of 
the subsequences.
Example 2:
Input: N = 7, arr[] = {1, 4, 2, 3, 
                       3, 2, 4}
Output: 0
Explanation: 
Increasing sequence can be :
            {1, 2, 3, 4}. 
Decreasing sequence can be :
             {4, 3, 2}.
Your Task:  
You don't need to read input or print anything. Complete the function minCount() which takes N and array arr as input parameters and returns the integer value
Expected Time Complexity: O(N^{3})
Expected Auxiliary Space: O(N^{3})
Constraints:
1 ≤ N ≤ 10^{2}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Starter code: #User function Template for python3
class Solution:
	def minCount(self, arr, n):
		# code here

Solutions:
class Solution:

	def minCount(self, l, n):
		l.insert(0, float('inf'))
		l.insert(0, -float('inf'))
		dp = [[[-1 for _ in range(n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]

		def ss(i, j, k):
			if k - 2 >= n:
				return 0
			if dp[i][j - 1][k - 2] != -1:
				return dp[i][j - 1][k - 2]
			if l[k] > l[i]:
				dp[i][j - 1][k - 2] = ss(k, j, k + 1)
			if l[k] < l[j]:
				if dp[i][j - 1][k - 2] == -1:
					dp[i][j - 1][k - 2] = ss(i, k, k + 1)
				else:
					dp[i][j - 1][k - 2] = min(dp[i][j - 1][k - 2], ss(i, k, k + 1))
			if dp[i][j - 1][k - 2] == -1:
				dp[i][j - 1][k - 2] = ss(i, j, k + 1) + 1
			else:
				dp[i][j - 1][k - 2] = min(dp[i][j - 1][k - 2], ss(i, j, k + 1) + 1)
			return dp[i][j - 1][k - 2]
		return ss(0, 1, 2)


MAX = 102

def countMin(arr, dp, n, dec, inc, i):
	if dp[dec][inc][i] != -1:
		return dp[dec][inc][i]
	if i == n:
		return 0
	if arr[i] < arr[dec]:
		dp[dec][inc][i] = countMin(arr, dp, n, i, inc, i + 1)
	if arr[i] > arr[inc]:
		if dp[dec][inc][i] == -1:
			dp[dec][inc][i] = countMin(arr, dp, n, dec, i, i + 1)
		else:
			dp[dec][inc][i] = min(countMin(arr, dp, n, dec, i, i + 1), dp[dec][inc][i])
	if dp[dec][inc][i] == -1:
		dp[dec][inc][i] = 1 + countMin(arr, dp, n, dec, inc, i + 1)
	else:
		dp[dec][inc][i] = min(1 + countMin(arr, dp, n, dec, inc, i + 1), dp[dec][inc][i])
	return dp[dec][inc][i]

def wrapper(arr, n):
	arr[MAX - 2] = 1000000000
	arr[MAX - 1] = -1000000000
	dp = [[[-1 for i in range(MAX)] for i in range(MAX)] for i in range(MAX)]
	return countMin(arr, dp, n, MAX - 2, MAX - 1, 0)

class Solution:

	def minCount(self, arr, n):
		for i in range(MAX):
			arr.append(0)
		return wrapper(arr, n)


class Solution:

	def minCount(self, nums, n):
		dp = [[[0 for _ in range(n + 2)] for __ in range(n + 2)] for ___ in range(n + 1)]
		for i in range(n + 1):
			for j in range(1, n + 2):
				for k in range(1, n + 2):
					if i > 0:
						dp[i][j][k] = dp[i - 1][j][k]
						if j == n + 1 or nums[i - 1] < nums[j - 1]:
							dp[i][j][k] = max(dp[i][j][k], dp[i - 1][i][k] + 1)
						if k == n + 1 or nums[i - 1] > nums[k - 1]:
							dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][i] + 1)
		return n - dp[n][n + 1][n + 1]


class Solution:

	def minCount(self, arr, n):
		inf = float('inf')
		dic = {}

		def dfs(mn, mx, i):
			if (mn, mx, i + 1) in dic:
				return dic[mn, mx, i + 1]
			if i >= n:
				return 0
			ans = inf
			if arr[i] < mx:
				ans = min(ans, dfs(mn, arr[i], i + 1))
			if arr[i] > mn:
				ans = min(ans, dfs(arr[i], mx, i + 1))
			ans = min(ans, 1 + dfs(mn, mx, i + 1))
			dic[mn, mx, i + 1] = ans
			return ans
		return dfs(-inf, inf, 0)


class Solution:

	def minCount(self, arr, n):
		dp = [[[float('inf') for k in range(n + 1)] for j in range(n + 1)] for i in range(n + 1)]
		val = self.mindp(arr, n, 1, float('-inf'), float('inf'), dp, 0, 0)
		return val

	def mindp(self, arr, n, st, incm, decmin, dp, incind, decind):
		if st == n + 1:
			return 0
		if not dp[st][incind][decind] == float('inf'):
			return dp[st][incind][decind]
		val = 1 + self.mindp(arr, n, st + 1, incm, decmin, dp, incind, decind)
		if incm < arr[st - 1]:
			val = min(val, self.mindp(arr, n, st + 1, arr[st - 1], decmin, dp, st, decind))
		if decmin > arr[st - 1]:
			val = min(val, self.mindp(arr, n, st + 1, incm, arr[st - 1], dp, incind, st))
		dp[st][incind][decind] = val
		return val