Given an array called A[] of sorted integers having no duplicates, find the length of the Longest Arithmetic Progression (LLAP) in it.
Example 1:
Input:
N = 6
set[] = {1, 7, 10, 13, 14, 19}
Output: 4
Explanation: The longest arithmetic 
progression is {1, 7, 13, 19}.
Example 2:
Input:
N = 5
A[] = {2, 4, 6, 8, 10}
Output: 5
Explanation: The whole set is in AP.
Your Task:
You don't need to read input or print anything. Your task is to complete the function lenghtOfLongestAP() which takes the array of integers called set[] and n as input parameters and returns the length of LLAP.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N^{2})
Constraints:
1 ≤ N ≤ 1000
1 ≤ set[i] ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Starter code: #User function Template for python3

class Solution:
    def lengthOfLongestAP(self, A, n):
        # code here

Solutions:
class Solution:

	def lengthOfLongestAP(self, A, n):
		if n <= 2:
			return n
		dp = [[2] * n for _ in range(n)]
		max_len = 2
		for j in range(n - 2, 0, -1):
			i = j - 1
			k = j + 1
			while i >= 0 and k < n:
				if A[i] + A[k] < 2 * A[j]:
					k += 1
				elif A[i] + A[k] > 2 * A[j]:
					dp[i][j] = 2
					i -= 1
				else:
					dp[i][j] = dp[j][k] + 1
					max_len = max(max_len, dp[i][j])
					i -= 1
					k += 1
		return max_len


from collections import defaultdict

class Solution:

	def lengthOfLongestAP(self, A, n):
		n = len(A)
		dp = [{} for _ in range(n)]
		if n <= 2:
			return n
		maxi = 0
		for i in range(n):
			for j in range(0, i):
				if i == 0:
					dp[i][0] == 1
				else:
					diff = A[i] - A[j]
					if diff in dp[j]:
						dp[i][diff] = dp[j][diff] + 1
					else:
						dp[i][diff] = 2
					if dp[i][diff] > maxi:
						maxi = dp[i][diff]
		return maxi


class Solution:

	def lengthOfLongestAP(self, A, n):
		if n <= 2:
			return n
		result_map = {i: {} for i in range(n + 1)}
		ans = 0
		dp = {}
		for i in range(len(A)):
			for j in range(i + 1, len(A)):
				diff = A[j] - A[i]
				dp[j, diff] = dp.get((i, diff), 1) + 1
				ans = max(ans, dp[j, diff])
		return ans


class Solution:

	def lengthOfLongestAP(self, A, n):
		a = A
		if n <= 2:
			return n
		ans = 0
		dp = [{} for i in range(n + 1)]
		for i in range(1, n):
			for j in range(0, i):
				diff = a[i] - a[j]
				cnt = 1
				if diff in dp[j]:
					cnt = dp[j][diff]
				dp[i][diff] = 1 + cnt
				ans = max(ans, dp[i][diff])
		return ans


from collections import defaultdict

class Solution:

	def lengthOfLongestAP(self, A, n):
		if n == 1:
			return 1
		dp = [defaultdict(int) for _ in range(n)]
		for i in range(1, n):
			for j in range(i - 1, -1, -1):
				dp[i][A[i] - A[j]] = dp[j][A[i] - A[j]] + 1
		return max((max((val for val in cnts.values())) for cnts in dp)) + 1


from collections import defaultdict

class Solution:

	def lengthOfLongestAP(self, A, n):
		dp = [defaultdict(int) for _ in range(n)]
		if n == 1:
			return 1
		res = 2
		for i in range(n - 1, -1, -1):
			for j in range(i + 1, n):
				diff = A[j] - A[i]
				if diff in dp[j]:
					dp[i][diff] += 1 + dp[j][diff]
					res = max(res, dp[i][diff])
				else:
					dp[i][diff] = 2
		return res


class Solution:

	def Solve(self, A, n, index, diff, memory):
		if index < 0:
			return 0
		if memory[index][diff] == -1:
			ans = 0
			for back in range(index - 1, -1, -1):
				if A[index] - A[back] == diff:
					ans = max(ans, 1 + self.Solve(A, n, back, diff, memory))
			memory[index][diff] = ans
		return memory[index][diff]

	def Bottom(self, a, n):
		diff = a[n - 1] - a[0]
		memory = [[0 for i in range(diff + 1)] for j in range(n)]
		if n <= 2:
			return n
		ans = 0
		for i in range(n):
			for j in range(0, i):
				current_count = 1
				current_diff = a[i] - a[j]
				if memory[j][current_diff]:
					current_count = memory[j][current_diff]
				memory[i][current_diff] = 1 + current_count
				ans = max(ans, 1 + current_count)
		return ans

	def lengthOfLongestAP(self, A, n):
		return self.Bottom(A, n)


class Solution:

	def lengthOfLongestAP(self, A, n):
		if len(A) == 1:
			return 1
		dp = [{} for _ in range(len(A))]
		maxi = 0
		for i in range(1, len(A)):
			for j in range(i):
				diff = A[i] - A[j]
				if diff in dp[j]:
					dp[i][diff] = dp[j][diff] + 1
				else:
					dp[i][diff] = 2
				maxi = max(dp[i][diff], maxi)
		return maxi


from functools import lru_cache
from collections import Counter, defaultdict
from sys import setrecursionlimit
setrecursionlimit(pow(10, 4))

class Solution:

	def lengthOfLongestAP(self, A, n):
		n = len(A)
		if n <= 2:
			return n
		i_map = defaultdict(list)
		for i in range(n):
			i_map[A[i]].append(i)

		@lru_cache(None)
		def rec(i, diff):
			next_num = A[i] + diff
			for next_i in i_map[next_num]:
				if next_i > i:
					return 1 + rec(next_i, diff)
			return 0
		max_len = 0
		for i in range(n):
			for j in range(i + 1, n):
				if A[i] == A[j]:
					max_len = max(max_len, len(i_map[A[i]]))
				else:
					max_len = max(max_len, 2 + rec(j, A[j] - A[i]))
		return max_len


class Solution:

	def lengthOfLongestAP(self, A, n):
		n = len(A)
		dp = [{} for i in range(n)]
		maxx = 0
		for i in range(n):
			for j in range(i):
				val = A[i] - A[j]
				if val in dp[j]:
					dp[i][val] = dp[j][val] + 1
				else:
					dp[i][val] = 1
				maxx = max(maxx, dp[i][val])
		return maxx + 1


class Solution:

	def lengthOfLongestAP(self, A, n):
		(dp, ans) = ({}, 1)
		for i in range(n):
			vi = A[i]
			for j in range(i):
				vj = A[j]
				dif = vi - vj
				tmp = dp[vi, dif] = 1 + dp.get((vj, dif), 1)
				ans = max(ans, tmp)
		return ans


class Solution:

	def lengthOfLongestAP(self, A, n):
		from collections import defaultdict
		dp = defaultdict(lambda : defaultdict(lambda : 1))
		ans = 1
		for i in range(n):
			vi = A[i]
			for j in range(i):
				vj = A[j]
				dif = vi - vj
				tmp = dp[vi][dif] = 1 + dp[vj][dif]
				ans = max(ans, tmp)
		return ans


def tabu(array):
	n = len(array)
	if n <= 2:
		return n
	ans = 0
	dp = [{} for _ in range(n + 1)]
	for i in range(1, n):
		for j in range(i):
			diff = array[i] - array[j]
			count = 1
			try:
				if dp[j][diff] != None:
					count = dp[j][diff]
			except:
				dp[j][diff] = None
			dp[i][diff] = 1 + count
			ans = max(ans, dp[i][diff])
	return ans

class Solution:

	def lengthOfLongestAP(self, array, n):
		return tabu(array)


class Solution:

	def lengthOfLongestAP(self, set, n):
		if n <= 2:
			return n
		L = [[2 for x in range(n)] for y in range(n)]
		llap = 2
		for i in range(n):
			L[i][n - 1] = 2
		for j in range(n - 2, 0, -1):
			i = j - 1
			k = j + 1
			while i >= 0 and k <= n - 1:
				if set[i] + set[k] < 2 * set[j]:
					k += 1
				elif set[i] + set[k] > 2 * set[j]:
					L[i][j] = 2
					i -= 1
				else:
					L[i][j] = L[j][k] + 1
					llap = max(llap, L[i][j])
					i -= 1
					k += 1
		return llap


from collections import defaultdict

class Solution:

	def lengthOfLongestAP(self, A, n):
		if n < 3:
			return n
		d = [defaultdict(int) for i in range(n)]
		fin = 1
		for i in range(n):
			ans = 1
			for j in range(i):
				diff = A[i] - A[j]
				ans = max(ans, d[j][diff] + 1)
				d[i][diff] = d[j][diff] + 1
			fin = max(fin, ans)
		return fin + 1


class Solution:

	def lengthOfLongestAP(self, A, n):
		if n <= 2:
			return n
		arr = A
		dp = {}
		max_length = 0
		dp[0] = {}
		for i in range(1, n):
			dp[i] = {}
			for j in range(0, i):
				diff = arr[i] - arr[j]
				if diff in dp[j]:
					dp[i][diff] = dp[j][diff] + 1
				else:
					dp[i][diff] = 2
				max_length = max(max_length, dp[i][diff])
		return max_length


class Solution:

	def lengthOfLongestAP(self, A, n):
		if not A:
			return 0
		if n <= 0:
			return 0
		if n == 1:
			return 1
		if n == 2:
			return 2
		dp = {}
		for i in range(1, len(A)):
			for j in range(i):
				dp[i, A[i] - A[j]] = dp.get((j, A[i] - A[j]), 1) + 1
		return max(dp.values())


class Solution:

	def lengthOfLongestAP(self, A, n):
		dp = {}
		for i in range(n):
			for j in range(i + 1, n):
				dp[j, A[j] - A[i]] = dp.get((i, A[j] - A[i]), 1) + 1
		return max(dp.values()) if dp else 1


from collections import OrderedDict

class Solution:

	def lengthOfLongestAP(self, A, n):
		if n <= 2:
			return n
		ans = 0
		maxdiff = max(A) - min(A)
		dp = [[-1 for col in range(maxdiff + 1)] for rows in range(n + 1)]
		for i in range(1, n):
			for j in range(i):
				diff = A[i] - A[j]
				cnt = 1
				if dp[j][diff] != -1:
					cnt = dp[j][diff]
				dp[i][diff] = 1 + cnt
				ans = max(ans, dp[i][diff])
		return ans


class Solution:

	def lengthOfLongestAP(self, A, n):
		if n == 1 or n == 2:
			return n
		d = {}
		for h in A:
			if h not in d:
				d[h] = 1
		m = 0
		dif = 0
		for g in range(n - 1):
			for s in range(g + 1, n - 1):
				c = 0
				i = A[s] - A[g]
				o = s + 1
				b = A[s]
				c += 2
				while i + b in d:
					c += 1
					b += i
				m = max(m, c)
		return m


from collections import defaultdict

class Solution:

	def lengthOfLongestAP(self, A, n):
		dp = [{} for _ in range(n)]
		ans = 0
		if n <= 2:
			return n
		for i in range(n):
			for j in range(i):
				diff = A[i] - A[j]
				if diff not in dp[j]:
					dp[i][diff] = 2
				else:
					dp[i][diff] = dp[j][diff] + 1
				ans = max(ans, dp[i][diff])
		return ans


class Solution:

	def lengthOfLongestAP(self, arr, n):
		from collections import defaultdict
		dp = {}
		mx = 0
		for i in range(n):
			dp[i] = defaultdict(int)
			for j in range(i):
				diff = arr[i] - arr[j]
				dp[i][diff] = dp[j][diff] + 1
				mx = max(dp[i][diff], mx)
		return mx + 1


class Solution:

	def lengthOfLongestAP(self, a, n):
		if n <= 2:
			return n
		dp = [dict() for i in range(n)]
		ans = 0
		for i in range(1, n):
			for j in range(i):
				diff = A[i] - A[j]
				count = 1
				if dp[j].get(diff):
					count = dp[j][diff]
				dp[i][diff] = count + 1
				ans = max(ans, dp[i][diff])
		return ans
		return max(dp)


from collections import defaultdict

class Solution:

	def lengthOfLongestAP(self, A, n):
		if n <= 2:
			return n
		dp = [dict() for i in range(n)]
		ans = 0
		for i in range(1, n):
			for j in range(i):
				diff = A[i] - A[j]
				count = 1
				if dp[j].get(diff):
					count = dp[j][diff]
				dp[i][diff] = count + 1
				ans = max(ans, dp[i][diff])
		return ans


class Solution:

	def countNumOfElemWithGivenDiff(self, setA, starting_elem, diff):
		cnt = 0
		next_elem_to_search = starting_elem + diff
		while True:
			if next_elem_to_search in setA:
				cnt += 1
			else:
				break
			next_elem_to_search = next_elem_to_search + diff
		return cnt + 1

	def lengthOfLongestAP(self, A, n):
		setA = set(A)
		best_cnt = 1
		for i in range(n):
			for j in range(i + 1, n):
				diff = A[j] - A[i]
				cnt = self.countNumOfElemWithGivenDiff(setA, A[i], diff)
				best_cnt = max(best_cnt, cnt)
		return best_cnt


def LLAP(arr, n):
	arr.sort()
	if n <= 2:
		return n
	dp = [[0 for i in range(n)] for j in range(n)]
	res = 2
	for i in range(n - 2, -1, -1):
		dp[i][n - 1] = 2
	for j in range(n - 2, -1, -1):
		i = j - 1
		k = j + 1
		while i >= 0 and k <= n - 1:
			if arr[i] + arr[k] > 2 * arr[j]:
				dp[i][j] = 2
				i = i - 1
			elif arr[i] + arr[k] < 2 * arr[j]:
				k = k + 1
			else:
				dp[i][j] = dp[j][k] + 1
				res = max(res, dp[i][j])
				i = i - 1
				k = k + 1
		while i >= 0:
			dp[i][j] = 2
			i = i - 1
	return res

class Solution:

	def lengthOfLongestAP(self, A, n):
		return LLAP(A, n)


class Solution:

	def lengthOfLongestAP(self, A, n):
		diff = A[-1] - A[0]
		dp = [[0 for i in range(n)] for i in range(diff + 1)]
		ans = 0
		for i in range(1, n):
			for j in range(i):
				d = A[i] - A[j]
				dp[d][i] = dp[d][j] + 1
				ans = max(ans, dp[d][i])
		return ans + 1


class Solution:

	def lengthOfLongestAP(self, nums, n):
		n = len(nums)
		if n <= 2:
			return n
		ans = 0
		dp = [{} for i in range(n)]
		for i in range(1, n):
			for j in range(0, i):
				diff = nums[i] - nums[j]
				if diff in dp[j]:
					dp[i][diff] = max(2, 1 + dp[j][diff])
				else:
					dp[i][diff] = 2
				ans = max(ans, dp[i][diff])
		return ans


class Solution:

	def lengthOfLongestAP(self, A, n):
		dp = []
		for x in range(n):
			a = dict()
			dp.append(a)
		ma = 1
		for x in range(n):
			if x > 0:
				for y in range(x):
					diff = A[x] - A[y]
					if dp[y].get(diff) is not None:
						dp[x][diff] = dp[y][diff] + 1
					else:
						dp[x][diff] = 2
					ma = max(ma, dp[x][diff])
		return ma


from collections import defaultdict

class Solution:

	def solve(self, index, diff, arr, dp):
		if index < 0:
			return 0
		if dp[index][diff] != -1:
			return dp[index][diff]
		ans = 0
		for i in range(index - 1, -1, -1):
			if arr[index] - arr[i] == diff:
				ans = max(ans, 1 + self.solve(i, diff, arr, dp))
			dp[index][diff] = ans
		return dp[index][diff]

	def solvenew(self, arr, n):
		dp = [defaultdict(int) for i in range(n + 1)]
		ans = 0
		for i in range(1, n):
			for j in range(i):
				diff = arr[i] - arr[j]
				cnt = 1
				if dp[j].get(diff):
					cnt = dp[j][diff]
				dp[i][diff] = 1 + cnt
				ans = max(ans, dp[i][diff])
		return ans

	def lengthOfLongestAP(self, A, n):
		if n <= 2:
			return n
		return self.solvenew(A, n)
		dp = [[-1 for i in range(max(A) - min(A) + 1)] for j in range(n + 1)]
		ans = 0
		for i in range(n):
			for j in range(i + 1, n):
				ans = max(ans, 2 + self.solve(i, A[j] - A[i], A, dp))
		return ans


class Solution:

	def lengthOfLongestAP(self, A, n):
		t = []
		for i in range(n):
			t.append({})
		ans = 1
		for i in range(1, n):
			for j in range(i):
				diff = A[i] - A[j]
				t[i][diff] = max(t[j].get(diff, 0) + 1, t[i].get(diff, 0))
				ans = max(ans, 1 + t[i][diff])
		return ans


from collections import defaultdict

class Solution:

	def lengthOfLongestAP(self, a, n):
		lengths = [{} for _ in range(n)]
		ans = 1
		for i in range(n - 1, -1, -1):
			for j in range(i + 1, n):
				r = a[j] - a[i]
				length = 1
				if r in lengths[j]:
					length = lengths[j][r]
				ans = max(ans, length + 1)
				lengths[i][r] = length + 1
		return ans


from collections import defaultdict

class Solution:

	def lengthOfLongestAP(self, A, n):
		if n <= 2:
			return n
		ans = [[0 for i in range(n)] for j in range(n)]
		for i in range(n):
			ans[i][n - 1] = 2
		for j in range(n - 2, 0, -1):
			i = j - 1
			k = j + 1
			while i >= 0 and k < n:
				if A[i] + A[k] < 2 * A[j]:
					k += 1
				elif A[i] + A[k] > 2 * A[j]:
					ans[i][j] = 2
					i -= 1
				else:
					ans[i][j] = ans[j][k] + 1
					i -= 1
					k += 1
			while i >= 0:
				ans[i][j] = 2
				i -= 1
		max1 = -1000000
		for i in range(n):
			for j in range(n):
				max1 = max(max1, ans[i][j])
		return max1