#P1121. 环状最大两段子段和
环状最大两段子段和
题目描述
给出一段长度为 的环状序列 ,即认为 和 是相邻的,选出其中连续不重叠且非空的两段使得这两段和最大。
输入格式
第一行是一个整数 ,表示序列的长度。
第二行有 个整数,描述序列 ,第 个数字表示 。
输出格式
一行一个整数,为最大的两段子段和是多少。
7
2 -4 3 -1 2 -4 3
9
提示
数据规模与约定
对于全部的测试点,保证 ,。
给出一段长度为 n 的环状序列 a,即认为 a1 和 an 是相邻的,选出其中连续不重叠且非空的两段使得这两段和最大。
第一行是一个整数 n,表示序列的长度。
第二行有 n 个整数,描述序列 a,第 i 个数字表示 ai。
一行一个整数,为最大的两段子段和是多少。
7
2 -4 3 -1 2 -4 3
9
对于全部的测试点,保证 2≤n≤2×105,−104≤ai≤104。