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

Question

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

комбинация должна быть такой, чтобы

1.ни один из элементов не является последовательным в основном наборе
2. элемент должен быть положительным* Какой должна быть логика, можно ли помочь?

Answer 1

Вы можете использовать DP.Рекурсивная идея выглядит следующим образом:

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]

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