# java 2ms O(n) solution using DP with detail explanation

• trying to find the relationship between f(n) and f(n - 1) when A[n] can be part of current arithmetic slice.

then easy to find that if A[n] can be the end of the current arithmetic slice, then the total number of arithmetic slices will be incremented by the length of current slice(including A[n]) - 3 + 1;

e.g.
when 1 2 3 --> (1, 2, 3) increment is 3 - 3 + 1 = 1
when 1 2 3 4 --> (2, 3, 4), (1, 2, 3,4), increment is 4 - 3 + 1 = 2
when 1 2 3 4 5 --> (3, 4, 5), (2, 3, 4, 5), (1, 2, 3, 4, 5), increment is 5 - 3 + 1 = 3.

so the first step is to loop and store the length of arithmetic.
second loop is to added up all the increments.

e.g. [1 2 3 4 0 0 7 8 9]
first loop [0 0 3 4 0 0 0 0 3];
second loop sum = (3 - 3 + 1) + (4 - 3 + 1) + 0 + 0 + 0 + 0 + (3 - 3 + 1) = 4

``````public class Solution {
public int numberOfArithmeticSlices(int[] A) {
if(A == null || A.length == 0) return 0;
int[] index = new int[A.length];
for(int i = 2; i < index.length; i++)
{
if(A[i] - A[i - 1] == A[i - 1] - A[i - 2])
{
if(index[i - 1] == 0) index[i] = 3;
else index[i] = index[i - 1] + 1;
}
else index[i] = 0;
}

int sum = 0;
for(int i = 0; i < index.length; i++)
{
if(index[i] != 0)
{
sum += index[i] - 3 + 1;
}
}
return sum;
}
}
``````

• the example you give was incorrect,it should be:
e.g. [1 2 3 4 0 0 7 8 9]
first loop [0 0 3 4 0 0 0 0 3];
second loop sum = (3 - 3 + 1) + (4 - 3 + 1) + (3 - 3 + 1) = 4

• This post is deleted!

• @vino2014zly sorry about the mistake. I correct the answer with more details. the code is correct.

Thanks.

• @Mino-De I must mistaken the numbers, just modified it with more detail.

and This is her. lol

Thanks.

• @linnn_hit Ha ha. Sorry. My bad.

• I got the same as you do. Using a cache for the differences.

``````public final int numberOfArithmeticSlices(final int[] a) {
if (2 >= a.length)
return 0;
final int[] diff = new int[a.length - 1];
// compute the length of differences, thus the length of diff is less 1
for (int i = 0; i < diff.length; i++)
diff[i] = a[i + 1] - a[i];

// dp[i] = the number of arithmetic slices so far at i
final int[] dp = new int[diff.length];
for (int i = 1; i < dp.length; i++)
// since it is difference, as long as 2 differences are the same
// it is a arithmetic slices
if(diff[i - 1] == diff[i])
// if the previous differences are also the same
// it means the length of slices now has been larger than 3
// give the following fact
// array -> the number of arithmetic slices | differences between i and (i - 1)
// {1}                -> 0  | nil
// {1, 2}             -> 0  | 0
// {1, 2, 3}          -> 1  | 1
// {1, 2, 3, 4}       -> 3  | 2
// {1, 2, 3, 4, 5}    -> 6  | 3
// {1, 2, 3, 4, 5, 6} -> 10 | 4
// every time, i-th element will increased by (dp[i - 1] - dp[i - 2] + 1)
if(1 < i && diff[i - 2] == diff[i - 1])
// dp[i] = dp[i - 1] + (dp[i - 1] - dp[i - 2] + 1);
dp[i] = 2 * dp[i - 1] - dp[i - 2] + 1;
else
dp[i] = dp[i - 1] + 1;
else
dp[i] = dp[i - 1];

return dp[diff.length - 1];
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.