Answer to Question #306207 in Python for oreo

Question

You are given an array of N non-negative integers: A₁, A₂, ..., A_N. An alternating subsequence is a subsequence in which the indices of any two consecutive elements differ by exactly two in the original array. That is, if A_i1, A_i2, ..., A_ik is some subsequence, then for it to be an alternating subsequence, (i₂ - i₁ = 2), (i₃ - i₂ = 2), and so on should all hold true. Among all alternating subsequences, find the one which has maximum sum of elements, and output that sum.

Answer 1

def pri_alt(arr, n):
 
    if (n == 1):
        return arr[0]
    min = arr[0]
    for i in range(1, n):
        if(min > arr[i]):
            min = arr[i]
    if(arr[0] == min):
        return arr[0]
    dec = [0 for i in range(n + 1)]
 
    inc = [0 for i in range(n + 1)]
 
    dec[0] = inc[0] = arr[0]
 
    flag = 0
 
    for i in range(1, n):
 
        for j in range(i):
            if (arr[j] > arr[i]):
 
                dec[i] = max(dec[i], inc[j] + arr[i])
 
                flag = 1
            elif (arr[j] < arr[i] and flag == 1):
 



                inc[i] = max(inc[i], dec[j] + arr[i])
 
    result = -2147483648
    for i in range(n):
 
        if (result < inc[i]):
            result = inc[i]
        if (result < dec[i]):
            result = dec[i]



    return result
 
pri_alt( [4, 3, 8, 5, 3, 8],6)
28