Link to the pdf version on UVa OJ
We are given an integer with N digits, we are asked to remove d digits from it so that the remaining number is maximum. For example given 123123, if we have to remove 3 digits, the maximum number we can get is 323 (we erase 1,2,1).
Look at the problem as keeping r = n - d digits, so we know the length of the final number. In a decimal system (or any other system) if we want to have the maximum number with r digits, which digit should we maximize first? Yes, the leftmost digit, so we do the same here. We keep r - 1 digits at the right end of input number, then from index 0 to index r - 1 we look for the biggest digit and we take that, now we have a new problem of the same form.
For example: number = 123123 and we want to keep r = 3 digits.
We put the 123123, we put 23 apart and try to find the maximum digit in the first 4 digits, we take the first 3.
number = 123, result = 3, r = 2 ===>>> number = 123, result = 32,
number = 3, result = 32, r = 1 ===>>> number = 3, result = 323
Work on this example yourself, number = 1059005838, r = 4, result would be 9838.
How do we find the maximum digit in range [i, j]? We precalculate a frequency array : frequency[idx][digit] means how many of digits we have from index 0 to index idx.
frequency[idx][digit] = frequency[idx-1][digit] + (value[idx] == digit). We just calculate frequency from left to right, each idx depends on idx-1. (Some people call this dynamic programming? :D)
Link to my own code for this problem
We are given an integer with N digits, we are asked to remove d digits from it so that the remaining number is maximum. For example given 123123, if we have to remove 3 digits, the maximum number we can get is 323 (we erase 1,2,1).
Look at the problem as keeping r = n - d digits, so we know the length of the final number. In a decimal system (or any other system) if we want to have the maximum number with r digits, which digit should we maximize first? Yes, the leftmost digit, so we do the same here. We keep r - 1 digits at the right end of input number, then from index 0 to index r - 1 we look for the biggest digit and we take that, now we have a new problem of the same form.
For example: number = 123123 and we want to keep r = 3 digits.
We put the 123123, we put 23 apart and try to find the maximum digit in the first 4 digits, we take the first 3.
number = 123, result = 3, r = 2 ===>>> number = 123, result = 32,
number = 3, result = 32, r = 1 ===>>> number = 3, result = 323
Work on this example yourself, number = 1059005838, r = 4, result would be 9838.
How do we find the maximum digit in range [i, j]? We precalculate a frequency array : frequency[idx][digit] means how many of digits we have from index 0 to index idx.
frequency[idx][digit] = frequency[idx-1][digit] + (value[idx] == digit). We just calculate frequency from left to right, each idx depends on idx-1. (Some people call this dynamic programming? :D)
Link to my own code for this problem
No comments:
Post a Comment