Блог

В программе нахождения максимальной суммы несмежных элементов, как мы можем напечатать элементы / индексы элементов, которые учитываются в окончательной сумме. Итак, здесь я прилагаю свой код для этого. Я использую динамическое программирование.

Я получил правильный ответ, когда существует только одна возможность возникновения максимальной суммы, например, у нас есть -1, 2, 4, 5. Таким образом, результат будет равен 5 и 2.

 n = int(input())
    tickets = list(map(int,input().split()))
    incl = 0
    excl = 0
    max_list = []
    for i in range(len(tickets)): 
        if excl>incl:
            new_excl = excl 
        else:
            new_excl = incl 
        incl = excl   tickets[i]
        excl = new_excl 
        if excl > incl:
            if len(max_list)>1 and (max_list[len(max_list)-1] - max_list[len(max_list)-2])==1:
                del max_list[len(max_list)-2]
        else:
            max_list  = [i] 
    if excl>incl:
        print(excl,max_list)
    else:
        print(incl,max_list)
  

Но я не получаю ответов при вводе, подобном этому: 4, 5, 4, 3. В этом вводе есть две возможности: 4 4 и 5 3. Я хочу напечатать ту возможность, которая имеет более высокие цифры, чем другая, с правой стороны. Итак, в этом примере с правой стороны 4 > 3, поэтому должна быть напечатана возможность 4. Но я получил все элементы в списке.

Я должен решить эту проблему. Это проблема из квалификационного раунда techgig’s code gladiators. Я нахожу ответ на свою проблему, но в любом случае это решение не дает мне 100 баллов. Я не проверял это для многих тестовых случаев, но вы можете проверить это, и если это не удается, пожалуйста, сообщите, чтобы я мог понять, в чем проблема.

 from itertools import combinations
for i in range(int(input())):
    n = int(input())
    tickets = list(map(int,input().split()))
    incl = 0
    excl = 0
    max_list = []
    for i in range(len(tickets)): 
        if excl>incl:
            new_excl = excl 
        else:
            new_excl = incl 
        incl = excl   tickets[i]
        excl = new_excl 
        if excl > incl:
            if len(max_list)>1 and (max_list[len(max_list)-1] - max_list[len(max_list)-2])==1:
                del max_list[len(max_list)-2]
        else:
            max_list  = [i] 
    if excl>incl:
        s=excl
    else:
        s=incl
    a=[]
    if 1 in [abs(t-s) for s,t in zip(max_list,max_list[1:])]:
        for m in range(2,n):
            for n in list(combinations(max_list, m)):
                if sum(tickets[b] for b in n)==s:
                    a =[n]
        l=[]
        index=[]
        for m in a:
            l =[tickets[m[1]]]
            index =[m[1]]
        v = index[l.index(max(l))]
        for m in a:
            if v in m:
                ans = m
                break
        for d in list(reversed(ans)):
            print(tickets[d],end='')
        print()
    else:
        max_list.reverse()
        for d in max_list:
            print(tickets[d],end='')
        print()