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()