Given an array A[] of size N, find the longest subsequence such that difference between adjacent elements is one.
Example 1:
Input: N = 7
A[] = {10, 9, 4, 5, 4, 8, 6}
Output: 3
Explaination: The three possible subsequences 
{10, 9, 8} , {4, 5, 4} and {4, 5, 6}.
Example 2:
Input: N = 5
A[] = {1, 2, 3, 4, 5}
Output: 5
Explaination: All the elements can be 
included in the subsequence.
Your Task:
You do not need to read input. Your task is to complete the function longestSubseq() which takes N and A[] as input parameters and returns the length of the longest such subsequence.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{3}
1 ≤ A[i] ≤ 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def longestSubsequence(self, N, A):

        # code here

Solutions:
class Solution:

	def longestSubsequence(self, n, a):
		L = [1 for i in range(n)]
		for i in range(n):
			for j in range(0, i):
				if a[i] == a[j] - 1 or a[i] == a[j] + 1:
					L[i] = max(L[i], L[j] + 1)
		mx = L[0]
		for i in range(0, n):
			mx = max(mx, L[i])
		return mx


class Solution:

	def longestSubsequence(self, N, A):
		if N == 1:
			return 1
		dp = [1] * N
		for i in range(N - 1, -1, -1):
			for j in range(i + 1, N):
				if abs(A[i] - A[j]) == 1:
					dp[i] = max(dp[i], 1 + dp[j])
		return max(dp)


class Solution:

	def dp_sol(self, N, A):
		dp = [1] * (N + 1)
		dp[0] = 0
		for i in range(2, N + 1):
			for j in range(1, i):
				if A[j - 1] - A[i - 1] == 1 or A[j - 1] - A[i - 1] == -1:
					dp[i] = max(dp[i], 1 + dp[j])
		return max(dp)

	def longestSubsequence(self, N, A):
		return self.dp_sol(N, A)


class Solution:

	def longestSubsequence(self, N, A):
		stateMap = [1 for _ in range(N)]
		for ind in range(1, N):
			maxVal = 1
			for lInd in range(ind):
				if A[ind] == A[lInd] - 1 or A[ind] == A[lInd] + 1:
					maxVal = max(maxVal, stateMap[lInd] + 1)
			stateMap[ind] = maxVal
		return max(stateMap)


class Solution:

	def longestSubsequence(self, n, A):
		t = [1] * n
		for i in range(1, n):
			for j in range(i):
				if abs(A[i] - A[j]) == 1 and t[i] < t[j] + 1:
					t[i] = t[j] + 1
		return max(t)


class Solution:

	def longestSubsequence(self, n, arr):
		dp = [1 for i in range(n)]
		for i in range(n):
			for j in range(i):
				if arr[i] == arr[j] + 1 or arr[i] == arr[j] - 1:
					dp[i] = max(dp[i], dp[j] + 1)
		result = 1
		for i in range(n):
			if result < dp[i]:
				result = dp[i]
		return result


class Solution:

	def longestSubsequence(self, n, a):
		dp = [1] * n
		m = 1
		for i in range(1, n):
			for j in range(i):
				if a[i] - a[j] == 1 or a[i] - a[j] == -1:
					dp[i] = max(dp[i], dp[j] + 1)
			m = max(m, dp[i])
		return m


class Solution:

	def longestSubsequence(self, N, A):
		if N == 1:
			return 1
		dp = [0 for _ in range(N)]
		res = 1
		for pos in range(N):
			dp[pos] = 1
			for idx in range(pos):
				if A[pos] == A[idx] + 1 or A[pos] == A[idx] - 1:
					dp[pos] = max(dp[pos], dp[idx] + 1)
			res = max(res, dp[pos])
		return res


class Solution:

	def longestSubsequence(self, n, arr):
		dp = [1] * n
		for ind in range(n):
			for prev in range(ind):
				if abs(arr[prev] - arr[ind]) == 1:
					dp[ind] = max(dp[ind], 1 + dp[prev])
		return max(dp)


class Solution:

	def longestSubsequence(self, N, A):
		dp = {}

		def rec(idx, prev, count):
			if idx < 0:
				return count
			if (idx, prev) in dp:
				return dp[idx, prev]
			pick = 0
			if prev == -1 or abs(A[idx] - A[prev]) == 1:
				pick = rec(idx - 1, idx, count + 1)
			npick = rec(idx - 1, prev, count)
			dp[idx, prev] = max(pick, npick)
			return dp[idx, prev]
		dp = [1] * N
		for i in range(N):
			for j in range(i):
				if abs(A[i] - A[j]) == 1:
					dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)


def solve(A, N):
	arr = [1] * N
	for i in range(1, N):
		for j in range(0, i):
			if abs(A[i] - A[j]) == 1:
				arr[i] = max(arr[i], arr[j] + 1)
	return max(arr)

class Solution:

	def longestSubsequence(self, N, A):
		return solve(A, N)


class Solution:

	def fun(self, idx, arr, n, prev, dp):
		if idx == n:
			return 0
		if dp[idx][prev + 1] != -1:
			return dp[idx][prev + 1]
		np = 0 + self.fun(idx + 1, arr, n, prev, dp)
		p = 0
		if prev == -1 or abs(arr[idx] - arr[prev]) == 1:
			p = 1 + self.fun(idx + 1, arr, n, idx, dp)
		dp[idx][prev + 1] = max(p, np)
		return dp[idx][prev + 1]

	def longestSubsequence(self, n, arr):
		dp = [1 for i in range(N + 1)]
		dp[0] = 1
		for i in range(1, N):
			for j in range(i):
				if abs(A[j] - A[i]) == 1:
					dp[i] = max(dp[i], dp[j] + 1)
		mx = -999
		for i in range(N):
			mx = max(dp[i], mx)
		return mx


class Solution:

	def longestSubsequence(self, n, a):
		res = [1] * n
		for i in range(1, n):
			for j in range(i):
				if abs(a[i] - a[j]) == 1:
					res[i] = max(res[i], 1 + res[j])
		return max(res)


class Solution:

	def longestSubsequence(self, N, A):
		h = {}
		ans = 0
		for i in range(N):
			l = 0
			if A[i] - 1 in h:
				l = h[A[i] - 1]
			if A[i] + 1 in h:
				l = max(l, h[A[i] + 1])
			h[A[i]] = l + 1
			ans = max(ans, h[A[i]])
		return ans


class Solution:

	def longestSubsequence(self, N, A):
		DP = [0] * N
		DP[0] = 1
		for i in range(1, N):
			temp = [0]
			for j in range(i):
				if abs(A[j] - A[i]) == 1:
					temp.append(DP[j])
			DP[i] = max(temp) + 1
		return max(DP)


class Solution:

	def longestSubsequence(self, N, A):
		dict = {}
		ans = 1
		for i in range(N):
			len = 1
			if A[i] - 1 in dict:
				len = max(len, dict[A[i] - 1] + 1)
			if A[i] + 1 in dict:
				len = max(len, dict[A[i] + 1] + 1)
			dict[A[i]] = len
			ans = max(ans, len)
		return ans


class Solution:

	def longestSubsequence(self, N, A):
		b = [0 for hm in range(N)]
		b[0] = 1
		for hm in range(1, N):
			for gm in range(hm):
				if abs(A[hm] - A[gm]) == 1:
					b[hm] = max(b[hm], b[gm] + 1)
			b[hm] = max(b[hm], 1)
		return max(b)


from collections import defaultdict

class Solution:

	def longestSubsequence(self, n, a):
		dp = defaultdict(lambda : 0)
		dp[a[0]] = 1
		c = 1
		for i in range(1, n):
			temp = 1
			if a[i] + 1 in dp or a[i] - 1 in dp:
				temp = 1 + max(dp[a[i] - 1], dp[a[i] + 1])
			c = max(c, temp)
			dp[a[i]] = temp
		return c


class Solution:

	def longestSubsequence(self, n, arr):
		d = {}
		d[arr[0]] = 1
		dp = [1] * n
		for i in range(1, n):
			ans1 = d.get(arr[i] - 1, 0)
			ans2 = d.get(arr[i] + 1, 0)
			if ans1 or ans2:
				dp[i] = 1 + max(ans1, ans2)
			d[arr[i]] = dp[i]
		return max(dp)


class Solution:

	def longestSubsequence(self, n, arr):
		dp = [1] * n
		for i in range(1, n):
			for j in range(0, i):
				if abs(arr[i] - arr[j]) == 1:
					dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)


class Solution:

	def longestSubsequence(self, N, a):
		LIS = [1] * N
		for i in range(N - 2, -1, -1):
			for j in range(i + 1, N):
				if abs(a[i] - a[j]) == 1:
					LIS[i] = max(LIS[i], 1 + LIS[j])
		return max(LIS)


class Solution:

	def longestSubsequence(self, N, A):
		n = N
		res = [1 for each in range(n + 1)]
		for i in range(n - 1, -1, -1):
			for j in range(i, n):
				if abs(A[j] - A[i]) == 1:
					res[i] = max(res[i], 1 + res[j])
		return max(res)


class Solution:

	def longestSubsequence(self, N, A):
		m = 0
		t = [1 for _ in range(N)]
		for i in range(N):
			for prev in range(i):
				if abs(A[i] - A[prev]) == 1:
					t[i] = max(t[i], 1 + t[prev])
			m = max(m, t[i])
		return m


class Solution:

	def longestSubsequence(self, N, A):
		dp = [1] * N
		maxi = float('-inf')
		for ind in range(N):
			for prev_ind in range(ind):
				if abs(A[prev_ind] - A[ind]) == 1 and 1 + dp[prev_ind] > dp[ind]:
					dp[ind] = 1 + dp[prev_ind]
			maxi = max(maxi, dp[ind])
		return maxi


from collections import defaultdict

class Solution:

	def longestSubsequence(self, N, A):
		d = defaultdict(lambda : 0)
		for item in A:
			d[item] = max(d[item], max(d[item - 1], d[item + 1]) + 1)
		return max(d.values())


class Solution:

	def longestSubsequence_ending_at_i(self, N, A, index, dp_arr):
		if dp_arr[index] != -1:
			return dp_arr[index]
		maximum = 1
		for i in range(index):
			if A[i] == A[index] - 1 or A[i] == A[index] + 1:
				maximum = max(maximum, 1 + self.longestSubsequence_ending_at_i(N, A, i, dp_arr))
		dp_arr[index] = maximum
		return maximum

	def longestSubsequence(self, N, A):
		dp_arr = [-1 for i in range(N)]
		max_subsequence = -1
		for i in range(N):
			max_subsequence = max(self.longestSubsequence_ending_at_i(N, A, i, dp_arr), max_subsequence)
		return max_subsequence


class Solution:

	def longestSubsequence(self, N, A):
		mapp = {}
		ma = 1
		for i in range(0, N):
			k = A[i]
			val = 0
			if k - 1 in mapp:
				val = mapp[k - 1]
			if k + 1 in mapp and mapp[k + 1] > val:
				val = mapp[k + 1]
			mapp[A[i]] = val + 1
			ma = max(ma, val + 1)
		return ma


class Solution:

	def longestSubsequence(self, N, A):
		dp = [1 for _ in range(N)]
		longestSubsequencesNumber = 1
		for i in range(len(A) - 2, -1, -1):
			for j in range(i + 1, len(A)):
				if abs(A[j] - A[i]) == 1:
					dp[i] = max(dp[i], 1 + dp[j])
			longestSubsequencesNumber = max(longestSubsequencesNumber, dp[i])
		return longestSubsequencesNumber


class Solution:

	def longestSubsequence(self, N, arr):
		dp = [1] * N
		for i in range(1, N):
			for j in range(0, i):
				if arr[i] == arr[j] + 1 or arr[j] - 1 == arr[i]:
					dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)


from collections import defaultdict

class Solution:

	def longestSubsequence(self, n, A):
		d = defaultdict(int)
		ans = 0
		for i in range(n):
			temp = 0
			if A[i] - 1 in d:
				temp = d[A[i] - 1]
			if A[i] + 1 in d:
				temp = max(temp, d[A[i] + 1])
			d[A[i]] = 1 + temp
			ans = max(ans, temp + 1)
		return ans


class Solution:

	def longestSubsequence(self, N, A):
		temp = [0] * len(A)
		for i in range(len(A)):
			sub = [temp[k] for k in range(i) if A[i] == A[k] - 1 or A[i] - 1 == A[k]]
			temp[i] = 1 + max(sub, default=0)
		return max(temp, default=0)


class Solution:

	def longestSubsequence(self, n, A):
		arr = [1 for i in range(n)]
		for i in range(1, n):
			for j in range(0, i):
				if A[i] - A[j] == 1 or A[i] - A[j] == -1:
					arr[i] = max(arr[i], arr[j] + 1)
		return max(arr)


class Solution:

	def solve(a, cur, prev, dp):
		if cur == len(a):
			return 0
		if dp[prev + 1][cur] != -1:
			return dp[prev + 1][cur]
		inc = 0
		if prev == -1 or abs(a[prev] - a[cur]) == 1:
			inc = 1 + Solution.solve(a, cur + 1, cur, dp)
		exc = Solution.solve(a, cur + 1, prev, dp)
		dp[prev + 1][cur] = max(inc, exc)
		return dp[prev + 1][cur]

	def longestSubsequence(self, n, arr):
		dp = [1 for _ in range(n)]
		maxi = 1
		for i in range(n):
			for j in range(i):
				if abs(arr[i] - arr[j]) == 1:
					dp[i] = max(dp[i], dp[j] + 1)
		for i in range(n):
			maxi = max(maxi, dp[i])
		return maxi


class Solution:

	def longestSubsequence(self, N, arr):
		dp = [1 for x in range(N)]
		maxi = 0
		for i in range(N):
			for prev in range(i):
				if abs(arr[i] - arr[prev]) == 1 and dp[i] < 1 + dp[prev]:
					dp[i] = 1 + dp[prev]
			maxi = max(maxi, dp[i])
		return maxi


from collections import defaultdict

class Solution:

	def longestSubsequence(self, n, arr):
		ans = 0
		hmap = defaultdict(int)
		for num in arr:
			hmap[num] = max(hmap[num - 1], hmap[num + 1]) + 1
			ans = max(ans, hmap[num])
		return ans


class Solution:

	def __init__(self):
		self.ans = 0
		self.dp = {}

	def longestSubsequence(self, N, A):
		if len(A) == 1:
			return 1

		def solve(array, i, j, sum):
			if j >= len(array) or i >= len(array):
				self.ans = max(self.ans, sum)
				return sum
			for k in range(j, len(array)):
				if abs(A[k] - A[i]) == 1:
					if (i, k) not in self.dp:
						b = sum + 1
						ss = solve(array, k, k + 1, b)
						self.dp[i, k] = b
					else:
						self.ans = max(self.ans, self.dp[i, k])
			self.ans = max(self.ans, sum)
			return sum
		for l in range(len(A) - 1):
			s = 1
			solve(A, l, l + 1, s)
		return self.ans


import collections

class Solution:

	def longestSubsequence(self, N, A):
		dp = collections.defaultdict()
		for number in A:
			if number + 1 in dp and number - 1 in dp:
				if dp[number + 1] > dp[number - 1]:
					dp[number] = dp[number + 1] + 1
				else:
					dp[number] = dp[number - 1] + 1
			elif number + 1 in dp:
				dp[number] = dp[number + 1] + 1
			elif number - 1 in dp:
				dp[number] = dp[number - 1] + 1
			else:
				dp[number] = 1
		return max(dp.items(), key=lambda x: x[1])[1]


class Solution:

	def longestSubsequence(self, N, A):
		res = []
		for i in range(N):
			m = 1
			for j in range(i):
				if abs(A[j] - A[i]) == 1 and res[j] >= m:
					m = res[j] + 1
			res.append(m)
		return max(res)


class Solution:

	def longestSubsequence(self, N, A):
		t = [0 for i in range(0, N + 2)]
		ans = 0
		for i in range(0, N):
			temp = 0
			for j in range(0, i):
				if abs(A[j] - A[i]) == 1:
					if t[j] > temp:
						temp = t[j]
			t[i] = 1 + temp
			if t[i] > ans:
				ans = t[i]
		return ans


class Solution:

	def longestSubsequence(self, n, a):
		maxx = 1
		dp = [1 for i in range(n)]
		for i in range(1, n):
			for j in range(i):
				if abs(a[i] - a[j]) == 1 and dp[i] < dp[j] + 1:
					dp[i] = dp[j] + 1
					maxx = max(dp[i], maxx)
		return maxx


from collections import defaultdict

class Solution:

	def longestSubsequence(self, N, A):
		d = defaultdict(lambda : 0)
		ans = 0
		for i in A:
			d[i] = 1 + max(d[i - 1], d[i + 1])
			ans = max(ans, d[i])
		return ans