Consider a piece of string (as in "rope", not as in "a bunch of characters"), which is folded back and forth on the real line. We can describe the shape of the string with a list of points it passes through (in order). For simplicity, we'll assume all of those points are integers.
Take as an example [-1, 3, 1, -2, 5, 2, 3, 4]
(note that not each entry implies a fold):
The string extending along the vertical direction is only for visualisation purposes. Imagine the string all flattened onto the real line.
Now here is the question: what is the greatest number of pieces this string can be cut into with a single cut (which would have to be vertical in the above picture). In this case, the answer is 6 with a cut anywhere between 2
and 3
:
To avoid ambiguities, the cut has to be performed at a non-integer position.
The Challenge
Given a list of integer positions a string is folded through, you're to determine the greatest number of pieces the string can be cut into with a single cut at a non-integer position.
You may write a full program or a function. You may take input via STDIN, command-line argument, prompt or function parameter. You may write output to STDOUT, display it in a dialog box or return it from the function.
You may assume that the list is in any convenient list or string format.
The list will contain at least 2 and no more than 100 entries. The entries will be integers, each in the range -231 ≤ pi < 231. You may assume that no two consecutive entries are identical.
Your code must process any such input (including the test cases below) in less than 10 seconds on a reasonable desktop PC.
Test Cases
All test cases are simply input followed by output.
[0, 1]
2
[2147483647, -2147483648]
2
[0, 1, -1]
3
[1, 0, -1]
2
[-1, 3, 1, -2, 5, 2, 3, 4]
6
[-1122432493, -1297520062, 1893305528, 1165360246, -1888929223, 385040723, -80352673, 1372936505, 2115121074, -1856246962, 1501350808, -183583125, 2134014610, 720827868, -1915801069, -829434432, 444418495, -207928085, -764106377, -180766255, 429579526, -1887092002, -1139248992, -1967220622, -541417291, -1617463896, 517511661, -1781260846, -804604982, 834431625, 1800360467, 603678316, 557395424, -763031007, -1336769888, -1871888929, 1594598244, 1789292665, 962604079, -1185224024, 199953143, -1078097556, 1286821852, -1441858782, -1050367058, 956106641, -1792710927, -417329507, 1298074488, -2081642949, -1142130252, 2069006433, -889029611, 2083629927, 1621142867, -1340561463, 676558478, 78265900, -1317128172, 1763225513, 1783160195, 483383997, -1548533202, 2122113423, -1197641704, 319428736, -116274800, -888049925, -798148170, 1768740405, 473572890, -1931167061, -298056529, 1602950715, -412370479, -2044658831, -1165885212, -865307089, -969908936, 203868919, 278855174, -729662598, -1950547957, 679003141, 1423171080, 1870799802, 1978532600, 107162612, -1482878754, -1512232885, 1595639326, 1848766908, -321446009, -1491438272, 1619109855, 351277170, 1034981600, 421097157, 1072577364, -538901064]
53
[-2142140080, -2066313811, -2015945568, -2013211927, -1988504811, -1884073403, -1860777718, -1852780618, -1829202121, -1754543670, -1589422902, -1557970039, -1507704627, -1410033893, -1313864752, -1191655050, -1183729403, -1155076106, -1150685547, -1148162179, -1143013543, -1012615847, -914543424, -898063429, -831941836, -808337369, -807593292, -775755312, -682786953, -679343381, -657346098, -616936747, -545017823, -522339238, -501194053, -473081322, -376141541, -350526016, -344380659, -341195356, -303406389, -285611307, -282860017, -156809093, -127312384, -24161190, -420036, 50190256, 74000721, 84358785, 102958758, 124538981, 131053395, 280688418, 281444103, 303002802, 309255004, 360083648, 400920491, 429956579, 478710051, 500159683, 518335017, 559645553, 560041153, 638459051, 640161676, 643850364, 671996492, 733068514, 743285502, 1027514169, 1142193844, 1145750868, 1187862077, 1219366484, 1347996225, 1357239296, 1384342636, 1387532909, 1408330157, 1490584236, 1496234950, 1515355210, 1567464831, 1790076258, 1829519996, 1889752281, 1903484827, 1904323014, 1912488777, 1939200260, 2061174784, 2074677533, 2080731335, 2111876929, 2115658011, 2118089950, 2127342676, 2145430585]
2
a reasonable desktop PC
rather ambiguous? \$\endgroup\$