Java verbose O(N) time O(1) space on DP/recursion inspired by Palindromic Substrings

• This is a solution inspired by one solution for the problem Palindromic Substrings. I personally refer to them all as Substring Counting problems. Good performance, verbose code but easy to understand.

``````public class Solution {
public int numberOfArithmeticSlices(int[] A) {
int res = 0, n = A.length, i = 0;
if (n < 3)
return 0;
while (i < n) {
int end = extendRun(A, i);
int length = end - i + 1;
i = end;
res += countSlices(length);
}
return res;
}

public int extendRun(int[] A, int start) {
int n = A.length;
if (start + 2 >= n)
return start + 1;
int diff = A[start + 1] - A[start];
int curr = start + 1;
while (curr + 1 < n && A[curr + 1] - A[curr] == diff)
curr++;
return curr;
}

public int countSlices(int length) {
if (length < 3)
return 0;
// use formula rather than directly count
int N = length - (3 - 1);
return N * (N + 1) / 2;
}
}
``````

Explanation by example:
for the example `1,1,2,3,4,5,6,5,4,3`, we find at `[1]`the longest slice `1,2,3,4,5,6` of length `6`. We can calculate the number of slices in it with the `countSlices` method. Then we restart the extending from the position of `6`, and found `6,5,4,3`. Again, count.

The `countSlices` method can also be implemented like:

``````    public int countSlices(int length) {
if (length < 3) return 0;
int sum = 0;
for (int i = length; i >= 3; i--)
sum += length - (i - 1);
return sum;
}
``````

Per my own submissions, the two ways of implementing this method does not make a noticeable difference in OJ feedback.

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