I think that the algorithm that you are using does not solve the problem you would like to solve. The main issue is that the criterion for extending the arithmetic sequence does not take into account the sequence itself. Consider for example:

A = [10, 20, 50, 60]

there are two sequences belonging to the difference -10, so the dict is actually not a good data structure to base your algorithm on, not at least the way you intend to.

EDIT

You can solve the problem in number of ways. A very direct, but not very efficient, approach is the following:

• sort all the elements (this is not strictly necessary, but it makes the rest more efficient)
• start by considering all elements
• determine if all elements are actually an arithmetic progression
  • compute the difference of consecutive elements only
  • if they all have the same value, then its an arithmetic progression
• if they are an arithmetic progression, you are done, if they are not, iteratively remove elements and repeat the above, until an arithmetic progression is found.

In code this, looks like:

import itertools


def is_arithmetic_progression(items):
    diffs = [x - y for x, y in zip(items[1:], items[:-1])]
    return diffs[1:] == diffs[:-1]


def skip_items(items, indexes):
    return [item for i, item in enumerate(items) if i not in indexes]


def lap_combs(items, sorting=True):
    if sorting:
        items = sorted(items)
    for i in range(len(items)):
        for indexes in itertools.combinations(range(len(items)), i):
            new_items = skip_items(items, indexes)
            if is_arithmetic_progression(new_items, False):
                return new_items


items = [83, 20, 17, 43, 52, 78, 68, 45]
longest_ap = lap_combs(items)
print(longest_ap)
# [78, 83]

items = [83, 20, 17, 43, 52, 78, 68, 45, 70]
longest_ap = lap_combs(items)
print(longest_ap)
# [20, 45, 70]

EDIT 2:

Note that this might be further optimized by analyzing the difference of the sorted items:

• compute all differences between any two items
• for a given difference, compute how many elements are within the items
• track the maximum number of elements found for a given item and element
• if, for a given difference, the items cannot contain more numbers than the maximum, skip it
• stop if the number of elements is more than half the number of items

In code, this looks like:

def seed_diff_len_to_seq(seed, diff, length):
    return [seed + diff * k for k in range(length)]


def lap_diffs(items):
    half_len_items = len(items) // 2
    span = max(items) - min(items)
    seed = 0
    max_seq_len = 0
    diff = None
    set_items = set(items)
    for item_i, item_j in itertools.combinations(sorted(items), 2):
        diff_ji = item_j - item_i
        if diff_ji == 0:
            seq_len = sum(1 for item in items if item == item_i)
        elif abs(diff_ji * max_seq_len) > span:
            continue
        else:
            seq_len = 2
            while item_i + diff_ji * seq_len in set_items:
                seq_len += 1
        if seq_len > max_seq_len:
            max_seq_len = seq_len
            seed = item_i
            diff = diff_ji
            if seq_len > half_len_items:
                break
    return seed_diff_len_to_seq(seed, diff, max_seq_len)

Benchmarking this (including @VPfB's solution as lap_maxprogr() and @rusu_ro1's solution as lap_dict(), while lap_combs() is at least 1 order of magnitude slower and not included in the plots) shows that lap_diffs() is the fastest (a soon as the number of input items is above approx. a dozen):

(Full analysis here.)

(Note that lap_diffs() uses substantially the same approach as lap_maxprogr() with some more optimizations).

Notice that:

1. There is 43 in your list and 68 - 43 = 25
2. There are multiple LPA with same diff

There are 2 bugs:

1. You check if the diff exists in d.keys(), but you do not check that if the numbers is in the LPA. e.g: when numbers are 43, 68 diff is 25, but your current list is [2, 20, 45]. In this case there are multiple LAP with same diff 25.
2. You inserted A[j], but not A[i], so you only inserted 68, not 43

you have to think that the difference btw numbers is not enough to take as a key, for examle 8 - 3 = 5, also 5 - 0 = 5

you can try:

def length_longest_AP(A):
    d = {}
    A.sort()
    for index_i, i in enumerate(A[:-1]):
        for index, j in enumerate(A[index_i + 1 :]):
            dif = j - i
            key = f'{i}_{index_i}_{dif}'

            if key in d:
                continue


            d[key] = [i, j]
            possible_next = j + dif
            try:
                current_index = index_i + 1 + index
                possible_next_one_index = current_index + A[current_index + 1:].index(possible_next)

                # avoiding repetitions 
                if current_index == possible_next_one_index:
                    possible_next_one_index = current_index + 1

            except ValueError:
                continue

            while True:
                d[key].append(possible_next)
                possible_next += dif
                try:
                    current_index = possible_next_one_index
                    possible_next_one_index = current_index + A[current_index + 1:].index(possible_next)

                    # avoiding repetitions 
                    if current_index == possible_next_one_index:
                        possible_next_one_index = current_index + 1

                except ValueError:
                    break


    return len(max(d.values(), key=len))

print(length_longest_AP([20,1,15,3,10,5,8]))
print(length_longest_AP([1,1,1,1,1,1,1,1,1,1]))
print(length_longest_AP([83,20,17,43,52,78,68,45]))

output:

4
10
2

Another approach. Consider each pair as a start of a progression and try to extend that progression.

Important optimization: if a progression contains at least half of total items it must be the longest possible prorgession.

import itertools

def maxprogr(items):
    # 2 or more numbers required to find any progression
    # if there are multiple maximums, the first one is returned 
    half = len(items) / 2
    pmax = (None, None, 0)
    for start, stop in itertools.combinations(sorted(items), 2):
        diff = stop - start
        if diff == 0:
            plen = sum(1 for x in items if x == start) 
        else:        
            plen = 2 
            while start + diff*plen in items:
                plen += 1
        if plen > pmax[2]:
            pmax = (start, diff, plen)
        if plen > half:
            break
    return pmax

# and some tests:
def print_maxprogr(items):
    print("MAX: start={0[0]}, diff=+{0[1]}, len={0[2]}".format(maxprogr(items)))

test1 = [20,1,15,3,10,5,8]
print_maxprogr(test1)
test2 = [83, 20, 17, 43, 52, 78, 68, 45, 70] 
print_maxprogr(test2)
test3 = [83, 20, 17, 43, 52, 78, 68, 45]
print_maxprogr(test3)
test4 = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
print_maxprogr(test4)

Test output:

MAX: start=5, diff=+5, len=4
MAX: start=20, diff=+25, len=3
MAX: start=17, diff=+3, len=2
MAX: start=1, diff=+0, len=10

(code was updated 1 hour after posting to fix a small error)