Наидлиннейшая арифметическая подпоследовательность с заданной разностью

Источник: https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/

1218. Longest Arithmetic Subsequence of Given Difference

Дан массив целых чисел и целое число, представляющее собой искомую разность. Вернуть наидленнейшую подпоследовательность в массиве такую, что разница между соседними элементами подпоследовательности равна искомой разности.

Подпоследовательность - это последовательность, которая может быть получена из исходного массива путем удаления из него нескольких (или 0) элементов, без изменения порядка в оставшихся элементах.

 

Пример 1:

Дано: arr = [1,2,3,4], difference = 1
Результат: 4
Пояснение: Наидлиннейшая подпоследовательность = [1,2,3,4]. В ней каждая пара соседних элементов отличается на значение difference.

Пример 2:

Дано: arr = [1,3,5,7], difference = 1
Результат: 1
Пояснение: Любой элемент массива является подпоследовательностью длины 1.

Пример 3:

Дано: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Результат: 4
Пояснение: Очевидно, что результат [7,5,3,1].

Ограничения:

• 1 <= arr.length <= 105
• -104 <= arr[i], difference <= 104

Идея решения

Допустим у нас есть элементы arr[i], arr[j], arr[k], i<j<k такие что

arr[j]-arr[i]=difference (1)
arr[k]-arr[j]=difference (2)

И пусть эти элементы не дают искомую разницу difference ни с какими другими желемнтами, которые им предшествуют.

Перепишем выражения (1) и (2): 

arr[j]-difference=arr[i] (3)
и arr[k]-difference=arr[j] (4)

Сканируя массив и проходя элементы i, j, k, мы сначала пройдем через элемент i, и проверим, встречался ли нам элемент arr[i]-difference. Нет, не встречался, поскольку arr[j]  идет после arr[i].

Однако мы помним, что сам по себе элемент образует подмассив, поэтому мы запомним, что наидлиннейшая подпоследовательность, в которую входит элемент arr[i] имеет длинну 1 (поскольку состоит, как минимум из arr[i]).

Затем в сканировании мы дойдем до элемента arr[j] и посмотрим, встречался ли нам arr[j]-difference, а это равно arr[i], как следуею из выражения (3). И этот эелемент нам встречался. И он входит в искомую подпоследовательность, которая пока что состоит из одного элемента. Но вместе arr[i] и arr[j]  образуют подпоследовательность длины 2. Поэтому запомним, что элементу arr[j] соответсвует подпоследовательность длины 2.

Наконец, мы доходим до элемета arr[k] и видим, что arr[k]-difference=arr[j](из выражения (4)). И поскольку элементу arr[j] соответвует подпоследовательность длины 2, то вместе с arr[k] мы получим подпоследовательность длины 3. И так далее.

Для запоминания, подпоследовательность какой длины соответсвует каждому отсканированному элементу, мы можем использовать структуре данных HashMap.

Хозяйке на заметку: где нужно смотреть сумму или разность, используй хэшмэп.

Java-имплементация

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        HashMap<Integer, Integer>seen = new HashMap<Integer, Integer>();
        int ans=0;
// итерация по элементам массива
        for (int i =0 ; i < arr.length; i++) {
            int x = arr[i]; //  пусть очередной элемент массива - это число х
// встречалось ли нам уже число x-difference?
// если нет, то сам элемент образует подпоследовательность длины 1;
// если да, то увеличиваем соответствующую ему длину на +1.
            int seendiff = seen.get(x-difference) == null ? 0 : seen.get(x-difference);
            seen.put(x, seendiff+1);
// если получившаяся на текущий момент подпоследовательность
// по длине превосходит локальный ответ  ans, то обновляем его
            ans = Math.max(ans, seen.get(x));
        }
        return ans; // возвращаем локальный ответ
    }
}