Imagine a concatenation of first 100
positive integers i.e. 12345678910111213...979899100
You are given a task to erase 96 digits of your choice, without changing the original order, then shrink the final sequence to eliminate blank spaces, striving to achieve largest possible result.
What is this maximal value and how was it derived?
The initial concatenation is 9 + 2*90 + 3 = 192 digits long, so erasing 96 will leave 96 as well.
At each point as we proceed from left to right we need to keep track of how many of the remaining digits we need to keep. For the given digit we are looking at in this sweep, we need to look ahead to see if any digit beyond is both higher than the one we're looking at and, if we wait until we get there to keep that one, there are enough digits remaining to satisfy the number still needed to complete the 96 we need to keep; if there is such a higher number then discard the digits until that number is reached; otherwise keep this one.
When you get to that higher number (if that's the decision made), the same decision procedure must be done again. That is, don't automatically assume this one is good just because it is higher than the one first looked at.
If, however, the decision was to keep the given digit being looked at, do so, subtracting 1 from the number still needed and advance to the next position and continue from there.
The program below follows that procedure and produces the following output:
I split up the original number below, with a row of carets (^) underneath each half to show which digits are kept. Below that is the resulting number that remains.
^ ^ ^ ^ ^^
Note that in this particular case it doesn't really matter that the 5 chosen was the one immediately following the last 9. However, the algorithm is written so that this 5 is chosen so as to allow more choice for subsequent tests, in cases, for example where everything after the given 5 (say) is lower than 5, as in ...54444451111111111111. Depending on how many more are required to be kept, choosing the second 5 instead of the first might (without further code) preclude continuing with the 4's, or actually including both 5's.
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
Open "leaving a maximal result.txt" For Output As #2
s$ = ""
For i = 1 To 100
s = s + LTrim(Str(i))
ptr = 1: need = 96: keep$ = ""
cmp$ = Mid(s, ptr, 1)
found = 0
For i = ptr + 1 To Len(s) + 1 - need
If Mid(s, i, 1) > cmp Then
ptr = i
found = 1
If found = 0 Then
keep = keep + cmp$
need = need - 1
kept(Len(keep)) = ptr
ptr = ptr + 1
Loop Until need = 0
Text1.Text = Text1.Text & s & crlf
Print #2, s
prev = 0
For i = 1 To 96
Text1.Text = Text1.Text & Space(kept(i) - prev - 1) & "^"
Print #2, Space(kept(i) - prev - 1) + "^";
prev = kept(i)
Text1.Text = Text1.Text & crlf & keep & crlf
Print #2, keep
Text1.Text = Text1.Text & crlf & " done"
Posted by Charlie
on 2017-08-25 10:47:40