Участник:Kiranov dmitry/task2

Материал из DISCOPAL
Перейти к: навигация, поиск

ссылка: https://leetcode.com/problems/number-of-longest-increasing-subsequence

 class Solution:
    def findNumberOfLIS(self, nums):
        b = nums
        a = []
        i = 0
        while i < (len(b)):
            if (b[i] != '[') and (b[i] != ',') and (b[i] != ' ') and (b[i] != ']'):
                if b[i] == '-':
                    i += 1 
                    a.append(-int(b[i]))
                else:
                    a.append(int(b[i]))
            i += 1
        if(len(a) == 0):
            return 0
        d = []
        p = []
        max_, res = 0, 0
        for i in range(len(a)):
            d.append(1)
            p.append(1)
            for j in range(i):
                if (a[j] < a[i]):
                    if (1 + d[j] > d[i]):
                        d[i] = 1 + d[j]
                        p[i] = p[j]
                    elif 1 + d[j] == d[i]:
                        p[i] += p[j]
            if(max_ == d[i]):
                res += p[i]
            elif(max_ < d[i]):
                max_ = d[i]
                res = p[i]
 
        return res