题解 | 最大连续子序列

def find_max_subseq(nums, n):
    """查找最大连续子序列"""
    # dp[i]表示以i结尾的最大子序列和
    dp = nums.copy()
    # 记录每个位置的起始索引
    start_idx = [i for i in range(n)]
    
    max_sum = dp[0]
    end = 0
    start = 0
    
    # 动态规划
    for i in range(1, n):
        if dp[i-1] + nums[i] > nums[i]:
            dp[i] = dp[i-1] + nums[i]
            start_idx[i] = start_idx[i-1]
        else:
            dp[i] = nums[i]
            start_idx[i] = i
            
        # 更新全局最大值
        if dp[i] > max_sum or (dp[i] == max_sum and start_idx[i] < start):
            max_sum = dp[i]
            end = i
            start = start_idx[i]
            
    return max_sum, nums[start], nums[end]

def main():
    while True:
        try:
            n = int(input())
            if n == 0:
                break
                
            nums = list(map(int, input().split()))
            
            # 处理全负数情况
            if all(x < 0 for x in nums):
                print(0, nums[0], nums[-1])
                continue
                
            max_sum, first, last = find_max_subseq(nums, n)
            print(max_sum, first, last)
            
        except EOFError:
            break

if __name__ == "__main__":
    main()