Ups and Down Sequence

updwn.py

'''
Count number of possible ways to create a sequence with following property

(1 3 4) "5" (4 2)
-- First part: Increasing
-- Second part: decreasing

'''

# no. of array items
N = input()

# Array
A = list(map(int, input().split(",")))

# max item
max_a = max(A)

# max item index to split array
max_i = A.index(max_a)


# count nis (number of increasing sub-sequences)
def countNis(arr):
    n = len(arr)
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if arr[j] > arr[i]:
                dp[i]+=dp[j]
    return sum(dp)

# if max at terminal then number of ways is 0
if A[-1] == max_a:
    print(0)

else:
    # count nis of left part 
    lups = countNis(A[0:max_i])

    # count nis of right array in reverse
    rups = countNis(A[max_i+1:][::-1])

    # print sum lups and rups
    print(lups + rups)