CODEWITHSUNDEEP
arraysalgorithm
Shashank
Shashank

Reputation: 180

Maximum sum of non-contiguous array elements that is divisible by K

Given an array ar with n elements, find the maximum sum in array that is divisible by K. The elements used in the sum need not be contiguous.

Example: For N = 4 and ar = [2,2,1,2] and K = 3, answer would be 6 (including elements 2, 2 and 2).

Upvotes: 3

Views: 500

Answers (1)

IVlad
IVlad

Reputation: 43477

This is just the subset sum problem.

Let dp[i] = true if we can build sum i and false otherwise.

dp[0] = true
s = 0
for each number x in the array:
  s += x
  for j = s down to x
    dp[j] = dp[j] OR dp[j - x]

Then find the largest j <= s such that j % k == 0 and dp[j] == true.

Upvotes: 3

Related Questions