Arithmetic Slices II — Subsequence

A zero-indexed array A consisting of N numbers is given. A subsequence slice of that array is any sequence of integers (P0, P1, …, Pk) such that 0 ≤ P0 < P1 < … < Pk < N.

A subsequence slice (P0, P1, …, Pk) of array A is called arithmetic if the sequence A[P0], A[P1], …, A[Pk-1], A[Pk] is arithmetic. In particular, this means that k ≥ 2.

The function should return the number of arithmetic subsequence slices in the array A.

Solution:

This is a dp problem let dp[i][j] represents the number of slices with difference j and ending at i.

Now the slices will be built up starting with 2 numbers because that is the minimum number of numbers you need to find the difference.

so for any 2 numbers at position y and y — 1

dp[y][number at y — number at y — 1] += 1

so to begin for any 2 number the above value is 1 . when we encounter another diff from y + 1 to y with diff x we find the number of diff ending at y with diff x. If there is no such distance this means this jump is being encountered for the first time hence we will follow the above equation otherwise it means we have encountered a third number in the triplet or the 4th or the 5th number so the number of slices would be equivalent to the number of pairs already encountered with diff x ending at y