Programme interro_rapide_30_minutes_2012_10_3c.py

#coding:latin-1
def plus_grande_sous_liste_rapide_r (li, i,j) :
    if i == j : return 0
    elif i+1 == j : return li[i],i,i+1
    
    milieu = (i+j)/2
    
    # on coupe le problème deux
    ma,ia,ja = plus_grande_sous_liste_rapide_r (li, i, milieu)
    mb,ib,jb = plus_grande_sous_liste_rapide_r (li, milieu, j)
    
    # pour aller encore plus vite dans un cas précis
    if ja == ib :
        total = ma+mb
        im,jm = ia,jb
    else :
        # on étudie la jonction
        im,jm = milieu,milieu+1
        meilleur = li[milieu]
        s = meilleur
        for k in range (milieu+1, j) :
            s += li[k]
            if s > meilleur :
                meilleur = s
                jm = k+1
                
        total = meilleur
        meilleur = li[milieu]
        s = meilleur
        for k in range (milieu-1, i-1, -1) :
            s += li[k]
            if s > meilleur :
                meilleur = s
                im = k
        
        total += meilleur - li[milieu]
            
    if   ma >= max(mb,total) : return ma,ia,ja
    elif mb >= max(ma,total) : return mb,ib,jb
    else : return total,im,jm
        
def plus_grande_sous_liste_rapide (li) :
    m,i,j = plus_grande_sous_liste_rapide_r (li,0,len(li))
    return li[i:j]
        
li = [ 4,-6,7,-1,8,-50,3]
m  = plus_grande_sous_liste_rapide(li)
print m   # affiche [7, -1, 8]

li = [1,2,3,4,5,-98,78,9,7,7]
m  = plus_grande_sous_liste_rapide(li)
print m   # affiche [79, 9, 7, 7]