What is the maximum value of any subsequence of array arr and module m?

Tip: dp you must consider the time complexity when filling in the form

subject

Array arr, whose element arr [i] > = 0. Sum of any subsequence of arr is sum. Given a number m, what is the maximum value of sum%m?

1, Examining questions

Example: for example, 1 3 2 4 = arr, m=5; What is the max value of sum%m for any subsequence?
Think violently:

If the number of i at any position is not added to sum, sum=0, sum%m=0
As long as arr[i] alone, sum%m=1 3 2 4
1+3=4，sum%m=4%4=0
1+3+2=6，sum%m=6%4=2
1+3+2+4=10，sum%m=10%4=2
3+2=5，sum%m=5%4=1
3+2+4=9，sum%m=9%4=1
2+4=6，sum%m=6%4=2
Therefore, the maximum value of all sum%m is 4;

This is the meaning of the title

2, Problem solving

The written test divide and conquer method AC is simple, O (2 ^ (n / 2)) < < o (2 * * n)

The purpose of divide and conquer is to greatly reduce the operation scale of a sub algorithm!
Divide arr into two parts of N/2: left and right
The maximum value on the left is max1, and the maximum value on the right is max2
Obviously, the sum%m value range of any subsequence is between 0 – m-1
The final max may only come from left, right, or a combination of two [high probability]

However, there are restrictions on how to fuse the maximum value on the left and right sides, that is, Max < = M-1
So you can take an element X on the left, then go to the right to find the value < = m-1-x, and add it up to max
understand?

Now, calculate the max self order sum of a part of arr separately, and directly enumerate the arr[index] at each position index? Instead, put the calculated value into an ordered table and kill it repeatedly to save space:
This code is the permutation and combination in dp. It can't be simpler

//Violence recursively enumerates a position i. do you want to put the sum%m freely selected from the position i---end into the ordered table
    public static void process(int[] arr, int m, int i, int end, int sum, TreeSet<Integer> set){
        if (i == end + 1) set.add(sum % m);//The violent decision to end+1 indicates that i--end has been decided and has been settled
        else {
            //Does sum want arri or not
            process(arr, m, i + 1, end, sum, set);//No, arri
            process(arr, m, i + 1, end, sum + arr[i], set);//To arri
        }
    }

Then, the written test algorithm AC divide and conquer process is as follows:
Find all possible values of sum%m on the left first
Then find all possible values of sum%m on the right
Finally, merge the left and right, and take sum%m of max

public static int maxModValue3(int[] arr, int m){
        if (arr == null || arr.length == 0) return 0;
        if (arr.length == 1) return arr[0] % m;

        int N = arr.length;
        int mid = (N - 1) >> 1;
        TreeSet<Integer> setLeft = new TreeSet<>();//Ascending order
        TreeSet<Integer> setRight = new TreeSet<>();//Ascending order

        process(arr, m, 0, mid, 0, setLeft);
        process(arr, m, mid + 1, N - 1, 0, setRight);//Collect enumeration results

        int max = 0;
        for (Integer left:setLeft) max = Math.max(max, left + setRight.floor(m - 1 - left));
        //Since setLeft must have 0 and setRight must have 0, when
        //If 0 is left, only the value closest to m-1 is left on the right
        //If m - 1 is left, only the value closest to 0 is left on the right
        //When left comes out of left, we must find the value close to m-1-lfet on the right
        //The goal is to find the max value closest to m-1, so three cases are enumerated in one sentence

Interview DP method 1, o(N*maxSum), if maxSum is not large

Define dp[i][j] this meaning:
Select any number from position 0 – i to form sum and put it into j. can it be formed? Can be true, otherwise it is false
In other words, j0 - maxSum. If the maxSum is not big, you can still play like this
We need to find all j on line N-1 [representing any number selected from 0 – N-1]. When dp[N-1][j] is true, let j%m take the maximum value,
This method is a little stupid, but the idea is feasible. Just fill in a form
o(N*maxSum) obviously maxSum is very large, so the complexity of filling in the form is too high
Look at the picture:

Column 0, all elements are not allowed, sum=0, so it is true
Line 0, do you have to look at jarr[0]? No. 0 is arr[0], which can form a j at most
The rest dp[i][j]:
Look at dp[i-1][j] what's going on, and now, i position, choose to i or not i, the two are or relationship

code:

 //In other words, instead of taking% first, we can get all the sums. The complexity is o(N*sumMax). When sumMax is too large, it will be discarded
    //How to fill in dpij? If you want i or don't want i, just count one

    public static int maxModValue(int[] arr, int m){
        if (arr == null || arr.length == 0 || m <= 0) return -1;

        int N = arr.length;
        int sumMax = arr[0];
        for (int i = 1; i < N; i++) {
            sumMax += arr[i];//Total cumulative sum
        }
        boolean[][] dp = new boolean[N][sumMax + 1];

        //In the first line, we just need to see if arr [0] can come up with j
        dp[0][arr[0]] = true;//The rest are all false. How can one number add up to others
        //In the first column, let's see if we can figure out j==0 from 0--i. of course, we can. It's over if we don't want one
        for (int i = 0; i < N; i++) {
            dp[i][0] = true;
        }
        //Anywhere ij, see if arri wants to
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < sumMax; j++) {
                dp[i][j] = dp[i - 1][j];//See if it's done when you don't i
                //Let's see how to ask j--arri for arri. The place has been arranged in i-1 above
                if (j - arr[i] >= 0) dp[i][j] = dp[i][j] | dp[i - 1][j - arr[i]];
            }
        }

        //Then look at the last line, which is the best after% is taken
        int max = 0;
        for (int j = 0; j < sumMax; j++) {
            if (dp[N - 1][j]) max = Math.max(max, j % m);
        }

        return max;
    }

Interview DP method 2, o(N*m), if maxSum is too large

Since maxSum may be too large, but if you first% m, the range will be limited to 0 – m-1, which greatly reduces the trouble of filling in the form
Define dp[i][j] this meaning:
Select any number from position 0 – i to form sum exactly, and then put sum%m into j. can it be formed? Can be true, otherwise it is false
Column 0, all elements are not required, sum=0, so all are true
Line 0, do you have to see j==arr[0]%m? Everything else is false
The rest dp[i][j]:
Look at dp[i-1][j] what's going on, and now, i position, choose to i or not i, the two are or relationship
However, it should be noted that since it is% m, you should be careful. If you want arr[i], you have to observe
Which x%m was just right before and the current arr[i]%m can make up m, so as to calculate j

(1) For example, when m=5,arri=3, j=7
If arri=3, then j=7=sum%m=(x+3)%5=x%5+3%5
Then x%5=j-3%5. It is required that there is a sum of x%5=4 on 0 – i-1, that is, we need to look at dp[i-1][j-arri%m]
Here, ensure that J - arr [i]% m > = 0

(2) Also note: when m=10,arri=3 and j=2
If arri=3, then J = 2 = sum% m = (x + 3)% 10 = * * x% 10 + 3% 10 = 9 + 3% 10 = 2**
Because j is always between 0 – m-1, how does x=9 come from, x=9=2+m-arri=2+10-3=9
So we need to look at dp[i-1][j+m-arri%m]

While (1) and (2) above are mutually exclusive, if it is (1), it will not be (2). Therefore, separate the following situations when filling in the form:
After filling in the table, from the index of j=m-1 – 0, the first true corresponds to j, which is the result we want

code:

public static int maxModValue2(int[] arr, int m){
        if (arr == null || arr.length == 0 || m <= 0) return -1;

        int N = arr.length;
        boolean[][] dp = new boolean[N][m];
        //first line
        dp[0][arr[0] % m] = true;//j is cumulative sum%m Oh, not cumulative sum
        //First column, none at all
        for (int i = 0; i < N; i++) {
            dp[i][0] = true;
        }
        //Fill in dpij in three cases
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = dp[i - 1][j];//No i
                //Use i, the two into one
                if (j - arr[i] % m >= 0) dp[i][j] = dp[i][j] | dp[i - 1][j - arr[i] % m];
                else dp[i][j] = dp[i][j] | dp[i - 1][j + m - arr[i] % m];
            }
        }

        int max = 0;
        for (int j = m - 1; j >= 0; j--) {
            if (dp[N - 1][j]) return j;//j is after taking the mold
        }

        return max;
    }

summary

Tip: important experience:

1) The written test divide and conquer method reduces the operation scale and is the easiest code to write
2) sum first%m can reduce the complexity of filling out forms