fork(1) download
  1. #!/usr/bin/env python
  2. from itertools import groupby
  3.  
  4. def longest_subarray(input_list):
  5. assert all(v > 0 for v in input_list)
  6. # sort (index, value) pairs by value O(n*log(n))
  7. # radix_sort(), count_sort() won't be O(n) if there is no limit on integers
  8. value = lambda (i, v): v
  9. L = sorted(enumerate(input_list), key=value)
  10.  
  11. no_duplicates = all(len(list(same_value_group)) == 1
  12. for _, same_value_group in groupby(L, key=value)) # O(n)
  13. start, end = 0, 0 # longest subarray indices
  14. if no_duplicates:
  15. # O(n/m) * O(m) = O(n) time; O(m) space
  16. # group consecutive runs (current = prev + 1)
  17. for _, g in groupby(enumerate(L), key=lambda (j, (i, v)): j - v):
  18. indices = [i for _, (i, v) in g] # O(m)
  19. assert all(input_list[currenti] == input_list[previ] + 1
  20. for currenti, previ in zip(indices[1:], indices))
  21. maxi, mini = indices[0], indices[0]
  22. for m, i in enumerate(indices):
  23. maxi, mini = max(i, maxi), min(i, mini)
  24. if maxi - mini == m and m >= (end - start):
  25. # found longer "continuous sequence"
  26. start, end = mini, maxi + 1
  27. else:
  28. assert 0, "input with duplicates is not supported"
  29. subarray = input_list[start:end]
  30. assert sorted(subarray) == range(min(subarray), max(subarray) + 1)
  31. return subarray
  32.  
  33. if __name__ == "__main__":
  34. L = map(int, raw_input().split())
  35. print "Input:", L,
  36. subarray = longest_subarray(L)
  37. print "Output:", subarray
  38. assert len(subarray) == 5
  39.  
Success #stdin #stdout 0.08s 8696KB
stdin
10 5 3 1 4 2 11 8 6 7
stdout
Input: [10, 5, 3, 1, 4, 2, 11, 8, 6, 7] Output: [5, 3, 1, 4, 2]