Python最多等和不相交连续子序列

def max_subsequence_groups(arr):
    """
    找到满足条件的最多连续子序列数目
    :param arr: 输入的数组
    :return: 满足条件的最多连续子序列数目
    """
    n = len(arr)
    prefix_sum = [0] * (n + 1)  # 前缀和数组
    sum_indices = {}  # 记录每个和对应的索引列表

    # 计算前缀和
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + arr[i]

    # 遍历所有可能的子序列
    max_count = 0
    for i in range(n):
        for j in range(i + 1, n + 1):
            current_sum = prefix_sum[j] - prefix_sum[i]  # 当前子序列的和
            if current_sum not in sum_indices:
                sum_indices[current_sum] = []
            # 检查当前子序列是否与之前的子序列不相交
            if not sum_indices[current_sum] or i >= sum_indices[current_sum][-1][1]:
                sum_indices[current_sum].append((i, j - 1))  # 记录子序列的起始和结束索引
                # 更新最大数目
                if len(sum_indices[current_sum]) > max_count:
                    max_count = len(sum_indices[current_sum])

    return max_count


def main():
    # 输入数组长度
    n = int(input("请输入数组长度: "))

    # 输入数组
    arr = list(map(int, input("请输入数组元素（用空格分隔）: ").split()))
    if len(arr) != n:
        raise ValueError("数组长度与输入的长度不一致！")

    # 计算满足条件的最多连续子序列数目
    result = max_subsequence_groups(arr)

    # 输出结果
    print(f"满足条件的最多连续子序列数目为: {result}")


# 运行主程序
if __name__ == "__main__":
    main()