import numpy as np

def maximum(s):
    M=s[0]
    for i in range(1,len(s)):
        if s[i]>M:
            M=s[i]
    return M

def doubleMax_v1(s):
    M=maximum(s)
    i=0
    while s[i]!=M:
        i+=1
    s.pop(i) #rappel : supprime l'élément d'indice i
    N=maximum(s)
    return M,N

def doubleMax(s):
    if s[1]>s[0]:
        top1=s[1]
        top2=s[0]
    else:
        top1=s[0]
        top2=s[1]
    for i in range(2,len(s)):
        if s[i]>top1:
            top2=top1
            top1=s[i]
        elif s[i]>top2:
            top2=s[i]
    return top1,top2

def remonteEnPlace(t,m):
    pos=m
    while pos>0 and t[pos-1]<t[pos]:
        t[pos-1],t[pos]=t[pos],t[pos-1]
        pos=pos-1
    return pos

def triIns(s):
    for i in range(len(s)):
        remonteEnPlace(s,i)

def kMeilleurs(s,k):
    zeBest=[]
    for i in range(k):
        zeBest.append(s[i])
        remonteEnPlace(zeBest,i)
    for i in range(k+1,len(s)):
        if s[i]>zeBest[k-1]:
            zeBest[k-1]=s[i]
            remonteEnPlace(zeBest,k-1)
    return zeBest

def estUnPic(h,i):
    #attention à l'ordre
    return i==0 or i==len(h)-1 or (h[i]>=h[i-1] and h[i]>=h[i+1])
        
def listePics(h):
    LP=[]
    for i in range(len(h)):
        if estUnPic(h,i):
            LP.append(i)
    return LP
    
def longueurArc(h,m):
    return np.sqrt(1+(h[m+1]-h[m])**2)

def longueurGrandeVallee_v1(h):
    LP=listePics(h)
    longMax=0
    for numeroPic in range(len(LP)-1):
        j=LP[numeroPic]
        longueur=0
        while j<LP[numeroPic+1]:
            longueur+=longueurArc(h,j)
            j+=1
        if longueur>longMax:
            longMax=longueur
    return longMax

def longueurGrandeVallee(h):
    longMax=0
    longueurCourante=0
    for i in range(len(h)-1):
        longueurCourante+=longueurArc(h,i)
        if longueurCourante>longMax:
            longMax=longueurCourante
        if estUnPic(h,i+1):
            longueurCourante=0
    return longMax
    
def codeCreux(V):
    T1=[]
    T2=[]
    n=len(V)
    for i in range(n):
        if V[i]!=0:
            T1.append(V[i])
            T2.append(i)
    return[T1,T2]
    
def decodeCreux(CC,N):
    val=CC[0]
    pos=CC[1]
    rep=[0 for i in range(N+1)]
    for i in range(len(pos)):
        rep[pos[i]]=val[i]
    return rep
    
def prodParScalaire(CC,a):
    val=CC[0]
    pos=CC[1]
    val2=[a*i for i in val]
    return [[val2,pos]]
    
def prodScal(CC1,CC2):
    val1=CC1[0]
    pos1=CC1[1]
    val2=CC2[0]
    pos2=CC2[1]
    i1,i2=0,0
    somme=0
    while i1<len(val1) and i2<len(val2):
        if pos1[i1]<pos2[i2]:
            i1+=1
        elif pos1[i1]>pos2[i2]:
            i2+=1
        else:
            somme+=val1[i1]*val2[i2]
            i1+=1
            i2+=1
    return somme
    
def somme(CC1,CC2):
    val1=CC1[0]
    pos1=CC1[1]
    val2=CC2[0]
    pos2=CC2[1]
    valS=[]
    posS=[]
    i1,i2=0,0
    while i1<len(val1) or i2<len(val2): # une des deux peut être épuisée
        #positions à comparer : pos1[i1] et pos2[i2] si elles existent
        if i1>=len(val1):#si on a épuisé la liste 1
            posS.append(pos2[i2])
            valS.append(val2[i2])
            i2+=1
        elif i2>=len(val2) or pos[i1]<pos[i2]:
            posS.append(pos1[i1])
            valS.append(val1[i1])
            i1+=1
        elif pos[i1]>pos[i2]:
            posS.append(pos2[i2])
            valS.append(val2[i2])
            i2+=1
        else: #égalité des indices
            posS.append(pos1[i1])
            valS.append(val1[i1]+val2[i2])
            i1+=1
            i2+=1
    return [valS,posS]