# Problem Kovancev v vrsti

# rešujemo nazaj!

# rekurzija 
def naj_vsota_R(i, K):
    '''največja možna vsota, ki jo lahko dobimo s kovanci K[i..n]'''
    n = len(K) - 1
    if i == n: return K[n]
    if i == n - 1: return max(K[n], K[n -1])
    vzamemo = K[i] + naj_vsota_R(i + 2, K)
    ne_vzamemo = naj_vsota_R(i + 1, K)
    return max(vzamemo, ne_vzamemo)

def naj_vsota(K):
    '''največja možna vsota, ki jo lahko dobimo s kovanci K[1..n]'''
    return naj_vsota_R(1, K)

def naj_vsota_tab(K):
    '''največja možna vsota, ki jo lahko dobimo s kovanci K[1..n]'''
    if len(K) < 3:
        return max(K[1:])  # 1 ali 2 kovanca
    n = len(K) - 1
    naj_vs = [0] * (n + 1)
    naj_vs[n] = K[n]
    naj_vs[n - 1] = max(K[n], K[n -1])
    for i in range(n - 2, 0, -1):
        vzamemo = K[i] + naj_vs[i + 2]
        ne_vzamemo = naj_vs[i + 1]
        naj_vs[i] = max(vzamemo, ne_vzamemo)
    return naj_vs[1]
            
            
if __name__ == '__main__':
    print('Osnovni testi\n')
    kovanci_1 = [42, 2, 3, 4, 2]
    print(naj_vsota(kovanci_1))
    print(naj_vsota_tab(kovanci_1))
    kovanci_2 = [42, 2, 3, 3, 4, 1]
    print(naj_vsota(kovanci_2))
    print(naj_vsota_tab(kovanci_2))
    kovanci_3 = [42, 2, 3, 3, 4, 3]
    print(naj_vsota(kovanci_3))
    print(naj_vsota_tab(kovanci_3))
    kovanci_4 = [42, 2, 3, 5, 2, 1, 3, 4, 3]
    print(naj_vsota(kovanci_4))
    print(naj_vsota_tab(kovanci_4))
    
    # nakljuèno koliko eltov
    koliko = 35
    print('\nRekurzija {0}'.format(koliko))
    import random
    kovanci = [random.randint(1, 10) for _ in range(koliko)]
    print(naj_vsota_tab(kovanci))
    print(naj_vsota(kovanci))
    
    # nakljuèno 50 eltov
##    koliko = 50
##    print('Rekurzija {0}'.format(koliko))
##    kovanci = [random.randint(1, 20) for _ in range(koliko)]
##    print(naj_vsota_tab(kovanci))
##    print(naj_vsota(kovanci))
    
##    # merjenje èasa
##    import timeit
##    koliko = 20
##    kovanci = [random.randint(1, 20) for _ in range(koliko)]    
##    print(timeit.timeit('naj_vsota_tab(kovanci)', globals=globals(), number = 100))
##    print(timeit.timeit('naj_vsota(kovanci)', globals=globals(), number = 100))