# 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