Given below is a sample problem:

Given n numbers such that their sum is not divisible by 4, remove k numbers such that after every removal, the sum of remaining numbers is not divisible by 4. Find the maximal sum of n-k remaining numbers.

Solution:

Divide the initial n numbers into 4 separate arrays corresponding to the 4 different remainders they leave when divided by 4. Now, sort them. Lets call these arrays a0, a1, a2, a3. Now, if say the sum of n numbers is divisible by 4.

f(k, a0, a1, a2, a3) = max {f(k-1, a0, a1+1,a2,a3), f(k-1,a0,a1,a2+1,a3), f(k-1,a0,a1,a2,a3+1) }

If the sum upon dividing with 4 gives a remainder of 1, we would have considered the arrays a0, a2 and a3.

Test case: n = 10 {44, 12, 45, 23, 22, 34, 47, 37, 50, 31}, Sum = 345

Answers:

k = 1, 333

k = 2, 311

k = 3, 279

k = 4, 257

k = 5, 223

k = 6, 186

k = 7, 142

k = 8, 97

k = 9, 50

k = 10, 0