Skip to content

4110. Find the Maximum Length of Valid Subsequence III πŸ”’

DifficultyMedium

Description

You are given an integer array nums and a positive integer k.

A subsequence of nums is valid if the sum of every pair of adjacent elements in the subsequence is divisible by k.

A subsequence of length 1 is always valid.

Return the length of the longest valid subsequence of nums.

 

Example 1:

Input: nums = [1,2,3,4,5], k = 3

Output: 4

Explanation:

  • Pick the subsequence [1, 2, 4, 5].
  • The adjacent sums are 1 + 2 = 3, 2 + 4 = 6, and 4 + 5 = 9, all divisible by 3.
  • No valid subsequence longer than 4 exists.

Example 2:

Input: nums = [5,10,15], k = 5

Output: 3

Explanation:

  • Pick the whole array [5, 10, 15].
  • The adjacent sums are 5 + 10 = 15 and 10 + 15 = 25, both divisible by 5.
  • Every element is a multiple of 5, so any two elements can be adjacent in a valid subsequence, and the answer is 3.

Example 3:

Input: nums = [1,3,5,7,9], k = 4

Output: 5

Explanation:

  • Pick the whole array [1, 3, 5, 7, 9].
  • The adjacent sums are 1 + 3 = 4, 3 + 5 = 8, 5 + 7 = 12, and 7 + 9 = 16, all divisible by 4.
  • The remainders alternate between 1 and 3, which add to 4, so the answer is 5.

 

Constraints:

  • 2 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 105

Solutions

Solution 1: Dynamic Programming

Thinking

Comparing the current element with every earlier candidate takes \(O(n^2)\) time. \(n\) is at most \(10^5\), so that enumeration does not fit.

Adjacent values sum to a multiple of \(k\) exactly when their remainders \(x\) and \(y\) satisfy \(y=(k-x)\bmod k\). The predecessor remainder is fixed by the current one, so a valid subsequence can only alternate between \(x\) and \(y\). When \(x=y\), every chosen element has the same remainder.

For one remainder it is enough to keep the rightmost index. A later element can attach only to the current rightmost index of the complementary remainder, and that chain is at least as long as any earlier index of the same remainder.

We therefore scan the array from left to right. A hash map \(\textit{last}\) stores the latest index of each remainder, and \(f[i]\) is the longest valid subsequence ending at index \(i\). On remainder \(x\), if \(y\) has already appeared, update \(f[i]\) with \(f[\textit{last}[y]]+1\), then set \(\textit{last}[x]\) to \(i\).

Let \(f[i]\) be the length of the longest valid subsequence ending at \(\textit{nums}[i]\), and initialize every \(f[i]\) to \(1\). The hash map \(\textit{last}\) stores the latest index of each remainder.

Scan the array from left to right. At index \(i\), set \(x=\textit{nums}[i]\bmod k\) and \(y=(k-x)\bmod k\). If remainder \(y\) is already in \(\textit{last}\), let \(j\) be that index and update \(f[i]\) to \(\max(f[i], f[j]+1)\). Then set \(\textit{last}[x]=i\).

The answer is the maximum value of \(f[i]\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of \(\textit{nums}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def maximumLength(self, nums: list[int], k: int) -> int:
        f = [1] * len(nums)
        last = {}
        ans = 1
        for i, x in enumerate(nums):
            x %= k
            y = (k - x) % k
            if y in last:
                j = last[y]
                f[i] = max(f[i], f[j] + 1)
                ans = max(ans, f[i])
            last[x] = i
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maximumLength(int[] nums, int k) {
        int n = nums.length;
        int[] f = new int[n];
        Arrays.fill(f, 1);
        Map<Integer, Integer> last = new HashMap<>();
        int ans = 1;
        for (int i = 0; i < n; i++) {
            int x = nums[i] % k;
            int y = (k - x) % k;
            if (last.containsKey(y)) {
                int j = last.get(y);
                f[i] = Math.max(f[i], f[j] + 1);
                ans = Math.max(ans, f[i]);
            }
            last.put(x, i);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> f(n, 1);
        unordered_map<int, int> last;
        int ans = 1;
        for (int i = 0; i < n; i++) {
            int x = nums[i] % k;
            int y = (k - x) % k;
            if (last.count(y)) {
                int j = last[y];
                f[i] = max(f[i], f[j] + 1);
                ans = max(ans, f[i]);
            }
            last[x] = i;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func maximumLength(nums []int, k int) int {
    n := len(nums)
    f := make([]int, n)
    for i := range f {
        f[i] = 1
    }
    last := map[int]int{}
    ans := 1
    for i, v := range nums {
        x := v % k
        y := (k - x) % k
        if j, ok := last[y]; ok {
            f[i] = max(f[i], f[j]+1)
            ans = max(ans, f[i])
        }
        last[x] = i
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function maximumLength(nums: number[], k: number): number {
    const n = nums.length;
    const f: number[] = new Array(n).fill(1);
    const last = new Map<number, number>();
    let ans = 1;
    for (let i = 0; i < n; i++) {
        const x = nums[i] % k;
        const y = (k - x) % k;
        if (last.has(y)) {
            const j = last.get(y)!;
            f[i] = Math.max(f[i], f[j] + 1);
            ans = Math.max(ans, f[i]);
        }
        last.set(x, i);
    }
    return ans;
}

Comments