algorithm - 配列内の要素の最大合計を見つける (ツイストあり)

Question

+ve と -ve integer を持つ配列を指定して、連続する 2 つの要素をスキップできないような最大合計を見つけます (つまり、先に進むにはそれらの少なくとも 1 つを選択する必要があります)。

例:-

10、20、30、-10、-50、40、-50、-1、-3

出力 : 10+20+30-10+40-1 = 89

Answer 1

動的計画法の使用を避けたい場合

• 最大合計を見つけるには、まず、すべての正の数を追加する必要があります。

• 負の要素のみをスキップします。2 つの連続する要素をスキップすることは許可されていないため、すべての連続する 負の要素を一時配列に配置し、以下に定義するように sum_odd_even 関数を使用して代替要素の最大合計を計算できます。

• 次に、そのようなすべての一時配列の最大値を、すべての正の数の合計に追加できます。そして、最終的な合計により、目的の出力が得られます。

コード：

def sum_odd_even(arr):
    sum1 = sum2 = 0
    for i in range(len(arr)):
        if i%2 == 0:
            sum1 += arr[i]
        else:
            sum2 += arr[i]
    return max(sum1,sum2)

input = [10, 20, 30, -10, -50, 40, -50, -1, -3]
result = 0
temp = []
for i in range(len(input)):
    if input[i] > 0:
        result += input[i]
    if input[i] < 0 and i != len(input)-1:
        temp.append(input[i])
    elif input[i] < 0:
        temp.append(input[i])
        result += sum_odd_even(temp)
        temp = []
    else:
        result += sum_odd_even(temp)
        temp = []

print result