给一组未排序的自然数，求其所有升序子序列的数量

count_sublists.py

# -*- coding: utf-8 -*-
"""
给一组未排序的自然数，求其所有升序子序列的数量
Ex1:
给定5个数 3 1 2 5 4
结果为 8
[3],[1],[1,2],[1,2,5],[2],[2,5],[5],[4]
Ex2: 
给定20个数 1 5 4 3 7 8 9 10 2 19 17 11 12 13 14 15 20 16 6 18
结果为 48
[1],[1,5],[1,5,4,3,7],[5],[4],[3],[3,7],[3,7,8],[3,7,8,9],[3,7,8,9,10],
[7],[7,8],[7,8,9],[7,8,9,10],[8],[8,9],[8,9,10],[9],[9,10],[10],
[2],[19],[17],[11],[11,12],[11,12,13],[11,12,13,14],[11,12,13,14,15],[11,12,13,14,15,20],[12],
[12,13],[12,13,14],[12,13,14,15],[12,13,14,15,20],[13],[13,14],[13,14,15],[13,14,15,20],[14],[14,15],
[14,15,20],[15],[15,20],[20],[16],[6],[6,18],[18]
"""

import math

#求组合的值，小于2时返回0
comb2 = lambda n: math.factorial(n)/math.factorial(n-2)/2 if n >= 2 else 0
#计算满足条件子序列数量
count_sub = lambda sub: comb2(len(sub))
cacl_subs = lambda subs: sum(map(count_sub, subs.values()))
#得到排序后的原索引
sort_key = lambda x: int(x[1])
sort_indexes = lambda arr: [i for i,_ in sorted(enumerate(arr), key=sort_key)]

#获得（索引）升序子序列
def get_subs(idxes):
    pointers = {}
    subs = {}
    for i in idxes:
        if pointers.has_key(i-1):
            p = pointers[i] = pointers[i - 1]
            subs[p].append(i)
        else:
            p = pointers[i] = i
            subs[p] = [i]
    return subs


if __name__ == '__main__':
    #> 20
    #> 1 5 4 3 7 8 9 10 2 19 17 11 12 13 14 15 20 16 6 18
    n = input()
    arr = raw_input().split()
    subs = get_subs(sort_indexes(arr))
    print  n + cacl_subs(subs)