最大子段和I

题目描述

给定一个长度为 $n$ 的整数序列，从中选出一段连续子段，使得该子段内所有元素的和最大。输出这个最大和。

输入

第一行一个整数 $n$，表示序列长度。 第二行 $n$ 个整数，表示该序列。

输出

输出一个整数，表示最大子段和。

样例输入

6
-2 1 -3 4 -1 2

样例输出

5

数据范围

$1\le n \le 10^3$

$-10^9\le a_i\le10^9$

---

最大子段和II

题目描述

给定长度为 $n$ 的整数序列，请选出两段互不相交的连续子段，将两段子段的元素和相加，求总和的最大值。

输入

第一行一个整数 $n$。 第二行 $n$ 个整数，表示序列。

输出

输出一个整数，表示选出两段不相交子段可以得到的最大总和。

样例输入

7
1 -2 3 4 -5 6 -7

样例输出

13

数据范围

$1\le n \le 10^3$

$-10^9\le a_i\le10^9$

---

最大子段和III

题目描述

给定长度为 $n$ 的整数序列，选出恰好 $k$ 段互不相交的连续子段，将所有选中子段的元素求和，求总和的最大值。

输入

第一行两个整数 $n,k$。 第二行 $n$ 个整数，表示序列。

输出

输出一个整数，表示恰好选 $k$ 段不相交子段的最大总和。

样例输入

8 3
2 -1 2 3 -10 5 6 -1

样例输出

17

数据范围

$1\le n \le 10^3,\;1\le k \le 10$

$-10^9\le a_i\le10^9$

---

最大子段和IV

题目描述

给定 $m$ 个整数序列，序列之间不能拼接合并，子段不允许跨序列选取。从全部序列中总共选出恰好 $k$ 段互不相交的连续子段（同一序列内部选出的子段也必须互不相交），求所有选中子段元素总和的最大值。

输入

第一行两个整数 $m,k$。 接下来 $m$ 行，每行第一个整数 $len_i$ 代表该序列长度，随后 $len_i$ 个整数为该序列的元素。

输出

输出一个整数，表示最大总和。

样例输入

2 2
3 5 -1 3
4 -2 4 1 -3

样例输出

12

样例解释

共有 $2$ 个互相独立的序列，不允许拼接，子段不能跨序列选取，需要总共恰好选出 $2$ 段互不相交的连续子段。

原始序列： 序列 1：$\{5,-1,3\}$ 序列 2：$\{-2,4,1,-3\}$

最优方案：

在序列 1 选取完整子段 $[1,3]，5+(-1)+3=7$。 在序列 2 选取子段 $[2,3]，4+1=5$。

两段分别取自不同序列，互相不重叠，总段数恰好等于 2。 总和：$7+5=12$。 因此最终答案为 12。

数据范围

$1\le m \le 10$，

$len_i \le 10^3$，

$1\le k \le 10$

$-10^9\le a_i\le10^9$

---

最大子段和V

题目描述

给定 $m$ 个整数序列。你最多可以执行 $p$ 次拼接操作：每次拼接可以把两个序列首尾相连合并成一个新序列，消耗一次拼接次数。拼接完成后，从得到的全部序列中总共选出恰好 $k$ 段互不相交的连续子段，求选中子段总和的最大值。

注意：子段可以取自拼接之后形成的长序列。

输入

第一行三个整数 $m,p,k$。 接下来 $m$ 行，每行第一个整数 $len_i$，之后 $len_i$ 个整数表示该序列元素。

输出

输出一个整数，表示最大总和。

样例输入

3 1 2
2 3 -1
3 2 5 -2
2 -4 6

样例输出

16

样例解释

共有 3 个原始序列，最多可以使用 1 次拼接操作，要求总共恰好选出 2 段互不相交的连续子段。 原始序列： 序列 1：$\{3,−1\}$ 序列 2：$\{2,5,−2\}$ 序列 3：$\{−4,6\}$ 最优方案：消耗 1 次拼接，将序列 3 与序列 2 拼接，得到合并后的长序列：$\{−4,6,2,5,−2\}$

在拼接后的长序列选取$1$段，子段$[2,4]$，元素为$\{6,2,5\}$，和为 $6+2+5=13$。 该子段跨越原本两个序列的边界，拼接之后允许跨原序列选取。 在序列 $1$ 选取 $1$ 段，取位置$[1,1]$，元素为$\{3\}$。 总段数恰好为$2$，拼接次数仅消耗 $1$ 次，满足题目的限制条件。 总和：$13+3=16$。

因此最终答案为 $16$。

数据范围

$1\le m \le 10$

$len_i \le 10^3$

$1\le k \le 10$

$0\le p \le \min(k-1,5)$

$-10^9\le a_i\le10^9$