Последовательность чисел называется арифметической, если она состоит не менее чем из трех элементов и если разница между любыми двумя последовательными элементами одинакова.
Например, это арифметическая последовательность:
1, 3, 5, 7, 9 7, 7, 7, 7 3, -1, -5, -9
Следующая последовательность не является арифметической.
1, 1, 2, 5, 7
Дан массив A с нулевым индексом, состоящий из N чисел. Срез этого массива — это любая пара целых чисел (P, Q), такая что 0 ‹= P ‹ Q ‹ N.
Срез (P, Q) массива A называется арифметическим, если последовательность:
A[P], A[p + 1], …, A[Q — 1], A[Q] является арифметической. В частности, это означает, что P + 1 ‹ Q.
Функция должна возвращать количество арифметических срезов в массиве A.
Пример:
A = [1, 2, 3, 4] return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.
Некоторые тестовые случаи:
[-7, -9, -11, -11, 11, 12, 13]
[-1, -3, -3, -4]
[1, 2, 3, 4, 7, 11, 15]
- Используйте DP для решения этой проблемы
2. Еще один шаг, выделение памяти не требуется.