логическая реализация для нахождения максимальной суммы непоследовательных притяжательных элементов массива

это массив с положительными и отрицательными целыми числами, предположим: 1,2,-1,3,5,1,-4,2,7, теперь мне нужно найти максимальную сумму всех комбинаций

сочетание должно быть таким, чтобы

<сильный>1. в основном наборе нет последовательных элементов
2. элемент должен быть положительным

изначально я думал реализовать это, разделив его на четные и нечетные, но на самом деле это не решение.

 ods=[]
 evns=[]
 ok=0;
 ek=1;
 for x in range(n):
            print(str(x)+"-"+str(ok)+"-"+str(ek))
            if x == ok and tkts[x]>0:
                ods.append(tkts[x])
                ok+=2
            elif x == ok and tkts[x] <= 0:
                ok+=1

            if x == ek and tkts[x]>0:
                evns.append(tkts[x])
                ek+=2
            elif x == ek and tkts[x] <= 0:
                ek+=1

какая должна быть логика, помогите пожалуйста.


python logic algorithm
person Swarna Sekhar Dhar    schedule 25.04.2019    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вы можете использовать ДП. Рекурсивная идея заключается в следующем

get_max(index):
    max = 0
    for i from index+2 to len:
        if(array[i] > 0)
            v = get_max(i)
            if (v > max) max = v
    return array[index]+max
get_max(0)

если мы запомним

x = [1,2,-1,3,5,1,-4,2,7]
dp = [0]*len(x)
ret = 0
for i in range(len(x)-3, -1, -1):
    max = 0
    for j in range(i+2, len(x)):
        if x[j] > 0 and dp[j]>max: max = dp[j]
    if x[i] > 0:
        dp[i] = max + x[i]
        if ret < dp[i]: ret = dp[i]

(Я не тестировал этот код, это просто идея)

person ksholla20    schedule 25.04.2019