Problem statement

https://binarysearch.com/problems/Largest-K-Divisible-Subsequence/

Solution

Let us keep in r maximum possible sums of subsets such that they have reminders 0, 1, .., k-1. In the beginning we need to define r[0] as 0 and all other elements as minus infinity. Then on each step we update r, adding num.

Complexity

It is O(n*k) for time and O(k) for space.

Code

class Solution:
    def solve(self, nums, k):
        r = [0] + [-float("inf")]*(k - 1)
        for num in nums:
            r2 = [0]*k
            for i in range(k):
                r2[(i + num)%k] = r[i] + num
            r = [max(a, b) for a, b in zip(r, r2)]

        return r[0]