비결정적 알고리즘

추측단계)
정렬된 배열 후보를 생성한다. O(n)
검증단계)
해당 수열이 오름차순인지 검증한다. O(n)
결과 계산)
차이의 최대치를 계산한다. O(n)

O(n)+O(n)+O(n)=O(n)
비결정적 알고리즘을 쓰지 말라는 조건은 없었음. ㅎ

http://www.mbchandak.com/wp-content/uploads/2014/12/Unit6_1.pdf
검증단계까지가 비결정적 정렬알고리즘.

(int list의 길이는 2 이상이라고 가정. 길이가 1 이하면 그냥 return 0)

주어진 int list에서 최솟값 m 찾기. O(n)
주어진 int list에서 최댓값 M 찾기. O(n)
int A=0이라고 선언 O(1)
int B=m이라고 선언 O(1)

1~2^16까지의 정수 i에 대해,      O(2^16)
 주어진 list에 B+i가 있는지 확인해서 있으면 O(n) : 
          A=max(A, i)         O(1)
          B=B+i                  O(1)
 B+i == M 이면 : return A                O(1)

따라서 O(2^16*n)=O(n)

ㅇㅇ bucket sort, radix sort 를 사용하면 되는 문제

#x: 배열
l = [False for i in range(65536)]
for v in x:
....l[v-1] = True

combo = 0
max_combo = 0
for i in range(65536):
....if l[i]:
........combo+= 1
........max_combo = max(max_combo,combo)
........combo=0
....else:
........combo+=1
max_combo=max(max_combo,combo)
return max_combo

이리 간단한걸 왜? ㅋㅋㅋㅋ
function max_distance(int[] m, int len) {
  max=0
  // count_sort(m, len)
  for(i=0; i<len; i=i+1)
    if(m[i+1] - m[i] > max) 
      max = m[i+1] - m[i]
  return max
}
정렬까지 O(n)으로 해내라고?

radix sort를 쓴다 ->O(dn)
선형 비교한다 ->O(n)