1218. Longest constant subsequence: using “sequence DP” in conjunction with “greedy”

“This is the fifth day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.

Topic describes

This is the 1218. Longest constant subsequence on LeetCode with medium difficulty.

Tag: greedy, sequence DP, state machine DP, hash table

You are given an integer array arr and an integer difference, please find and return the length of the longest arithmetic subsequence in ARR, the difference between the adjacent elements of the subsequence is equal to difference.

A subsequence is a sequence derived from an ARR by removing some elements or none without changing the order of the rest of the elements.

Example 1:

Input: ARr = [1,2,3,4], difference = 1 Output: 4 Explanation: The longest arithmetic subsequence is [1,2,3,4].Copy the code

Example 2:

Input: arr = [1,3,5,7], difference = 1 Output: 1 Explanation: The longest arithmetic subsequence is any single element.Copy the code

Example 3:

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2 output: 4 explanation: the longest arithmetic subsequence is [7,5,3,1].Copy the code

Tip:

• 
  $1 <= arr.length <= 10^5$
• 
  $-10^4 <= arr[i], difference <= 10^4$

State machine sequence DP + hash table

define
$f[i][j]$(
$j$ 非
$0$ 即
$1$) before representative
$i$Number, and number
$i$The choice of the number is
$j$, the length of the longest differential subsequence obtained.

Final answer for Max ⁡ (f (n – 1) [0], f (n – 1) [1]), Max (f (n – 1) [0], f (n – 1) [1]) Max (f (n – 1) [0], f (n – 1) [1]), At the same time, we have clearly initialization conditions f [0] [0] = 0 f [0] [0] = 0 f [0] [0] = 0 and f [0] [1] = 1 f [0] [1] = 1 f [0] [1] = 1.

F [I][j]f[I][j]f[I][j]f[I][j]

• F [I][0]f[I][0]f[I][0]f[I][0] : if the third position is not selected, then the maximum length is the result of the previous position. That is:

• F [I][1] F [I][1] F [I][1]

  • Arr arr arr [I] [I] [I] a subsequence of independence, at this time are: [I] [1] f = 1 f [I] [1] = 1 f [I] [1] = 1;
  • Arr arr arr [I] [I] [I] followed in a number of the, because given the difference differencedifferencedifference, Differenceprev =arr[I]− DifferencePrev =arr[I] -differencePrev =arr[I]−difference The (subscript subscript is lower than iii) position, and then transferred from the position, that is: [I] [1] f = f [hash [prev]] [1] + [1] [I] 1 f = f [hash [prev]] [1] + [1] [I] 1 f = f [hash [prev]] of [1] + 1;

  Easy to prove: If there are multiple locations with the value prevPrevPrev, select one of the locations with the highest subscript (subscript less than iii) for the transfer and the result will not be worse than the optimal location. So we “covet” the location with the largest subscript (subscript less than iii), which leads us to use a “hash table” to record the value information of the processed location during the migration.

  To sum up, we have:

Code (using arrays as hash tables in P2P2P2) :

class Solution {
    public int longestSubsequence(int[] arr, int d) {
        int n = arr.length;
        Map<Integer, Integer> map = new HashMap<>();
        int[][] f = new int[n][2];
        f[0] [1] = 1;
        map.put(arr[0].0);
        for (int i = 1; i < n; i++) {
            f[i][0] = Math.max(f[i - 1] [0], f[i - 1] [1]);
            f[i][1] = 1;
            int prev = arr[i] - d;
            if (map.containsKey(prev)) f[i][1] = Math.max(f[i][1], f[map.get(prev)][1] + 1);
            map.put(arr[i], i);
        }
        return Math.max(f[n - 1] [0], f[n - 1] [1]); }}Copy the code

class Solution {
    int N = 40009, M = N / 2;
    public int longestSubsequence(int[] arr, int d) {
        int n = arr.length;
        int[] hash = new int[N];
        Arrays.fill(hash, -1);
        int[][] f = new int[n][2];
        f[0] [1] = 1;
        hash[arr[0] + M] = 0;
        for (int i = 1; i < n; i++) {
            f[i][0] = Math.max(f[i - 1] [0], f[i - 1] [1]);
            f[i][1] = 1;
            int prev = arr[i] - d;
            if(hash[prev + M] ! = -1) f[i][1] = Math.max(f[i][1], f[hash[prev + M]][1] + 1);
            hash[arr[i] + M] = i;
        }
        return Math.max(f[n - 1] [0], f[n - 1] [1]); }}Copy the code

• Time complexity: Let NNN be array length, and a total of N ∗2n * 2n∗2 states need to be calculated, and the complexity of each state transition is O(1)O(1)O(1). The overall complexity is O(n)O(n)O(n)
• Space complexity: O(n)O(n)O(n)

Optimization state definition

It is not difficult to find that we define multiple one-dimensional states to distinguish whether a value at a certain position is selected or not, in order to correctly transfer the situation where the third bit is selected.

In fact, we can easily do this using the hash table itself.

The adjustment state is defined as: f[I]f[I]f[I] is the longest constant subsequence length obtained when considering the first iii number (the third number must be selected).

F [I]f[I]f[I]

• Arr [I]arr[I]arr[I] independently becomes a subsequence, where f[I]=1f[I]=1f[I]=1;
• Arr arr arr [I] [I] [I] followed in a number of the, because given the difference differencedifferencedifference, Differenceprev =arr[I]− differencePrev =arr[I]−difference, [j]arr[j]arr[j] arr[j]arr[j]arr[j] arr[j]arr[j]arr[j] arr[j]arr[j]arr[j] arr[j]arr[j]arr[j] arr[j]arr[j] f[i]=hash[prev]+1f[i] = hash[prev] + 1f[i]=hash[prev]+1;

To sum up, we have (hashhashhash initialized to 000) :

Code (using arrays as hash tables in P2P2P2) :

class Solution {
    public int longestSubsequence(int[] arr, int d) {
        int ans = 1;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : arr) {
            map.put(i, map.getOrDefault(i - d, 0) + 1);
            ans = Math.max(ans, map.get(i));
        }
        returnans; }}Copy the code

class Solution {
    int N = 40009, M = N / 2;
    public int longestSubsequence(int[] arr, int d) {
        int ans = 1;
        int[] hash = new int[N];
        for (int i : arr) {
            hash[i + M] = hash[i - d + M] + 1;
            ans = Math.max(ans, hash[i + M]);
        }
        returnans; }}Copy the code

• Time complexity: Let NNN be the length of array, there are NNN states to be calculated, and the complexity of each state transition is O(1)O(1)O(1). The overall complexity is O(n)O(n)O(n)
• Space complexity: O(n)O(n)O(n)

The last

This is the No.1218 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.