# 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 % 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? No. 0 is arr, 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;
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  can come up with j
dp[arr] = 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] = 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%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[arr % 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] = 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

Posted by Mad Mick on Sat, 16 Apr 2022 14:49:00 +0930