Return to Question

Given a set of numbers, find the length of the longest arithmetic progression in it.

Examples: numbers = new int[]{1, 3, 4, 5, 7, 8, 9} The length is 5, and the sequence is 1, 3, 5, 7, 9 with increment 2 in each iteration.

Given a sorted array, find the length of the longest arithmetic progression in it.

Examples: numbers = new int[]{1, 3, 4, 5, 7, 8, 9} The length is 5, and the sequence is 1, 3, 5, 7, 9 with increment 2 in each iteration.

The idea of applying test case analysis to tutor myself to learn how to solve the algorithm using dynamic programming method step by step, later on I can apply this technique to other dynamic programming algorithm as well.

The idea of applying test case analysis is to tutor myself to learn how to solve the algorithm using dynamic programming method step by step, later on I can apply this technique to other dynamic programming algorithm as well.

Base case is to set lookup[i][n-1] = 2 for any i from 0 to n - 1.

0 1 2 3 4 5 6
_________________________
0| 0 0 0 0 0 0 2
1| 0 0 0 0 0 0 2
2| 0 0 0 0 0 0 2
3| 0 0 0 0 0 0 2
4| 0 0 0 0 0 0 2
5| 0 0 0 0 0 0 2
6| 0 0 0 0 0 0 2

Checking out 8, found 7, 8, 9. We have lookup[4][5] = lookup[5][6] + 1.
0 1 2 3 4 5 6
_________________________
0| 0 0 0 0 0 0 2
1| 0 0 0 0 0 0 2
2| 0 0 0 0 0 0 2
3| 0 0 0 0 0 0 2
4| 0 0 0 0 0 3 2
5| 0 0 0 0 0 0 2
6| 0 0 0 0 0 0 2

Base case is to set lookup[i][n-1] = 2 for any i from 0 to n - 1.

0 1 2 3 4 5 6
_________________________
0| 0 0 0 0 0 0 2
1| 0 0 0 0 0 0 2
2| 0 0 0 0 0 0 2
3| 0 0 0 0 0 0 2
4| 0 0 0 0 0 0 2
5| 0 0 0 0 0 0 2
6| 0 0 0 0 0 0 2

Checking out 8, found 7, 8, 9. We have lookup[4][5] = lookup[5][6] + 1. In other words, 8 is the average of 7 and 9, since 8 = (7 + 9)/ 2. This is also a simple example of AVERAGE subproblem.

0 1 2 3 4 5 6
_________________________
0| 0 0 0 0 0 0 2
1| 0 0 0 0 0 0 2
2| 0 0 0 0 0 0 2
3| 0 0 0 0 0 0 2
4| 0 0 0 0 0 3 2
5| 0 0 0 0 0 0 2
6| 0 0 0 0 0 0 2