# Lo spessore di un segmento di vettore non vuoto v[l,r) e' la massima differenza tra due valori in v[l,r)
# cioe' max(v[l,r)) - min([v[l,r))
# Dato un vettore v, e un valore C, trovare il segmento piu' lungo di spessore al piu' C.

# soluzione 1: algoritmo ignorante: \Theta(n^3)
def maxSegSpessCIgn(v, C):
	L, l, r = 1, 0, 1
	for i in range(len(v)):
		for j in range(i+1, len(v)): # \Theta (n^2) cicli
			spess = max(v[i:j]) - min(v[i:j]) # \Theta(j-i), in media \Theta(n/2) = \Theta(n)
			if spess <= C and j - i > L:
				L, l, r = j-i, i, j
	return L, l, r			

# soluzione 2: se conosco min(v[i,j)) e' facile calcolare min(v[i,j+1)). 
# Simile per max... \Theta(n^2)
def maxSegSpessCBetter(v, C):
	L, l, r = 1, 0, 1
	for i in range(len(v)):
		maxs, mins = v[i], v[i]
		for j in range(i+2, len(v)):
			maxs, mins = max(maxs, v[j-1]), min(mins, v[j-1])
			spess = maxs - mins
			if spess <= C and j - i > L:
				L, l, r = j-i, i, j
	return L, l, r			

# soluzione 3: usando il fatto che lo spessore e' monotono,
# mi allargo a destra se spess < C, mi stringo a sinistra altrimenti... 
# non miglioro il caso pessimo, perche' non c'e' un modo facile di 
# ricalcolare min, max quando ci si stringe, ma molte volte esco prima
# questo algoritmo e' O(n^2)

# questo algoritmo puo' essere reso \Theta(n log n) usando una struttura dati 
# (heap o ABR bilanciato) che permette di calcolare max e min del nuovo intervallo in \Theta(log n)
# in entrambi i casi (allargamento a destra o restrizione a sinistra, vedi slides)
def maxSegSpessCSmart(v, C):
	L, l, r = 1, 0, 1
	maxs, mins, i, j = v[0], v[0], 0, 1
	while j<len(v):  # \Theta(n) iterazioni, osservare che i < j nel ciclo e i + j < 2*n
		spess = maxs - mins
		if spess <= C:
			if j - i > L:
				L, l, r = j - i, i, j
			maxs, mins = max(maxs, v[j]), min(mins, v[j])
			j = j + 1
		else:
			i = i + 1
			maxs, mins = max(v[i:j+1]), min(v[i:j+1]) # \Theta(j-i), in media \Theta(n/2) = \Theta(n)
	return L, l, r
		
def maxSegCavallo(v, l, r, m, C, mini, maxi):
	# si sfrutta il fatto che max(v[l,r)) conoscendo ml = max(v[l,m)) e mr = max(v[m,r)) 
	# e' semplicemente max(ml, mr). Similmente per il min. E quindi per lo spessore
    # fase 1: per k < m,  maxi[k] sara' il massimo dell'intervallo [k,m) (idem per mini)
    #         per k >= m, maxi[k] sara' il massimo dell'intervallo [m,k) (idem per mini)
    # in questo modo posso calcolare spess(v[l,r]=max(maxi[l], maxi[r]) - min(mini[l], mini[r])), 
    # a patto che l < m e r >=m
		maxi[m-1], mini[m-1] = v[m-1], v[m-1]
		k = m-2
		while k >= l:
			maxi[k], mini[k] = max(v[k],maxi[k+1]), min(v[k],mini[k+1])
			k = k - 1
		maxi[m], mini[m] = v[m], v[m]
		k = m+1
		while k < r:
			maxi[k], mini[k] = max(v[k],maxi[k-1]), min(v[k],mini[k-1])
			k = k + 1
	# fase 2: si cerca il segmento di spessore < C maggiore a cavallo di m		
		Lc, lc, rc = 1, m, m
		i, j = l, m
		while i<m and j<r:
			spess = max(maxi[i],maxi[j]) - min(mini[i],mini[j])
			if spess <= C and j - i + 1 > Lc:
				Lc, lc, rc = j - i + 1, i, j+1
			if spess <= C:
				j = j + 1
			else:
				i = i + 1
		return Lc, lc, rc				

def maxSegSpessCDeI(v, l, r, C, mini, maxi):
	# caso base: segmenti lunghi 1
	if l + 1 == r: 
		return 1, l, r
	m = (l + r) // 2	
	Ll, ll, rl = maxSegSpessCDeI(v, l, m, C, mini, maxi)  # T(n/2)
	Lr, lr, rr = maxSegSpessCDeI(v, m, r, C, mini, maxi)  # T(n/2)
	Lc, lc, rc = maxSegCavallo(v, l, r, m, C, mini, maxi) #\Theta(n)

	# si sceglie il piu' lungo dei 3 segmenti:
	if Ll >= Lr:
		if Ll >= Lc:
			return Ll, ll, rl 
		else:
			return Lc, lc, rc
	else:		
		if Lr >= Lc:
			return Lr, lr, rr 
		else:
			return Lc, lc, rc

def maxSegSpessC(v, C):
	mini = [None for _ in range(len(v))]
	maxi = [None for _ in range(len(v))]
	return maxSegSpessCDeI(v, 0, len(v), C, mini, maxi)

v = [-2, 4, 1, 6, -1, 10, 3, 4, -3]
C = 7
L, l, r = maxSegSpessCIgn(v, C)
print L, v[l:r]
L, l, r = maxSegSpessCBetter(v, C)
print L, v[l:r]
L, l, r = maxSegSpessCSmart(v, C)
print L, v[l:r]
L, l, r = maxSegSpessC(v, C)
print L, v[l:r]