安贤量化笔试 20220420

series = [1, 5, 8, 2, 11, 4, 2, 6, 7, 5, 4]
N = 4
threshold = 15

n = len(series)
res = []

import itertools
for num in range(n):
    for i in itertools.combinations(series, num + 1):
        if len(list(i)) >= 2 and len(list(i)) <= N and sum(list(i)) < threshold and list(i) not in res and all(x<y for x, y in zip(list(i), list(i)[1:])) and list(i) == sorted(list(i)):
            res.append(list(i))

print(res)

def find_sub_series(series, N, threshold):
    n = len(series)
    dp = [[] for i in range(n)]  # dp[i]表示以i结尾的最长递增子序列
    dp[0] = [series[0]]
    for i in range(n):
        for j in range(i):
            if series[i] > series[j]:
                if len(dp[i]) <= len(dp[j]) + 1:
                    dp[i] = dp[j] + [series[i]]
                else:
                    dp[i] = dp[i]
    # 去重 + 删除长度大于1的
    tmp = []
    for i in range(n):
        if dp[i] not in tmp and len(dp[i]) > 1:
            tmp.append(dp[i])

    # 长度大于等于3的进行拆分
    chai = []
    import itertools

    for i in range(len(tmp)):
        if len(tmp[i]) == 2:
            if sum(tmp[i]) < threshold:
                chai.append(tmp[i])
        if len(tmp[i]) > 2:
            n = len(tmp[i])
            for num in range(n):
                for j in itertools.combinations(tmp[i], num+1):
                    if len(list(j)) >= 2 and len(list(j)) <= N and sum(list(j)) < threshold and list(j) not in chai:
                        chai.append(list(j))
    return chai

print(find_sub_series([1, 5, 8, 2, 11, 4, 2, 6, 7, 5, 4], 4, 15))