In a string, an increasing run is a block of consecutive characters in which each character is greater than the one before ("abcd" in "xabcdab"). Write LongestRun, which reads words until the end of the input and, for each, finds the longest increasing run (the first one in case of a tie) twice, counting the character comparisons:
- every start — from each position, extend the run as far as it goes;
- one pass — walk through the string once, remembering where the current run began.
Print the run, its position and length, the two counts, and whether the two methods agree. For the input
welcome abcdefghijklmnopqrstuvwxyz zyxwvutsrq aabbccdd x
the program prints
welcome: longest increasing run "el" at index 1, length 2
comparisons: 8 (every start) versus 6 (one pass); same answer: true
abcdefghijklmnopqrstuvwxyz: longest increasing run "abcdefghijklmnopqrstuvwxyz" at index 0, length 26
comparisons: 325 (every start) versus 25 (one pass); same answer: true
zyxwvutsrq: longest increasing run "z" at index 0, length 1
comparisons: 9 (every start) versus 9 (one pass); same answer: true
aabbccdd: longest increasing run "ab" at index 1, length 2
comparisons: 10 (every start) versus 7 (one pass); same answer: true
x: longest increasing run "x" at index 0, length 1
comparisons: 0 (every start) versus 0 (one pass); same answer: true
Which input makes the first method quadratic? Which one makes it as fast as the second?