Proficient.
Put your skills to the test.

Problem summary

Choose any subsequence, not necessarily consecutive, whose sum is divisible by K. Maximize its length; the empty subsequence is allowed.

Constraints

All input numbers, including N and K, are positive and less than 1000.

Worked example

An independently prepared example for this explanation.

7 5
1 2 1 2 2 1 4

5

Solution analysis

1. Let best[r] be the maximum length of a subsequence of the processed prefix with sum remainder r modulo K. Initially only remainder 0 is possible, with length zero; all others are unreachable.
2. For a new value v, copy the old table to represent skipping it. For each reachable old remainder r, update the new remainder (r+v) mod K with best[r]+1. Use a fresh table to prevent selecting the current element multiple times.
3. In the sample, subsequence 1,2,1,2,4 has sum 10 and length 5. The total sum is 13. Removing a 1 and a 2 leaves five elements with divisible sum, while removing just one value cannot remove remainder 3 because no element has remainder 3. Thus six and seven are impossible.

Why it works

Every subsequence of a prefix either excludes its final element or includes it after a subsequence of the shorter prefix. The two transitions cover these cases exactly and retain the greatest length for each remainder. Thus the final state for remainder zero is optimal.

Watch out. This is not a contiguous-subarray problem. Initialize unreachable remainders below zero and use an old-state copy for each element.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<algorithm>
// Algorithm: Let best[r] be the maximum length of a subsequence of the processed prefix with sum
// remainder r modulo K.
using namespace std;
int main(){
    int count,modulus;
    cin>>count>>modulus;
    vector<int>best(modulus,-1000000);
    best[0]=0;
    for(int i=0;i<count;i++){
        int value;
        cin>>value;
        vector<int>next=best;
        for(int remainder=0;remainder<modulus;remainder++){
            if(best[remainder]>=0){
                int destination=(remainder+value)%modulus;
                next[destination]=max(next[destination],best[remainder]+1);
            }
        }
        best.swap(next);
    }
    cout<<best[0]<<'\n';
}