最大递增子序列和 - 南京理工大学

对于一个序列 b_i，当满足条件 b < b < ... < b_S 时，我们称该序列为递增序列。

给定一个整数序列 (a, a, ..., a_N)，我们可以从中选取若干元素构成其上升子序列 (a_i, a_i, ..., a_iK)，其中下标满足 1 ≤ i < i < ... < i_K ≤ N。

举例说明：对于序列 (1, 7, 3, 5, 9, 4, 8)，存在多个递增子序列，例如 (1, 7)、(3, 4, 8) 等。其中，和最大的递增子序列为 (1, 3, 5, 9)，总和为 18。

需要注意的是，最长的递增子序列其元素和未必最大。例如在序列 (100, 1, 2, 3) 中，最长递增子序列为 (1, 2, 3)，但最大递增子序列和为 100，对应子序列即为 (100)。

本题要求：针对每组输入序列，计算出其最大递增子序列的元素和。

输入格式

• 包含多组测试数据。
• 每组数据第一行为一个整数 N（1 ≤ N ≤ 1000），表示序列长度。
• 第二行包含 N 个整数，表示序列元素，每个数的范围在 0 到 10000 之间（可重复）。

输出格式

对每组测试数据，输出一个整数，表示该序列的最大递增子序列和。

输入样例

7
1 7 3 5 9 4 8

输出样例

18

堆排序问题 - 南京理工大学

题目要求：给定一个整数序列，将其调整为大顶堆结构，并求出所需进行的最小交换次数。

大顶堆是一种特殊的完全二叉树结构，其中父节点的值始终不小于其子节点的值。通过一系列元素交换操作，可以将任意序列转换为合法的大顶堆。

输入格式

• 第一行输入一个整数 n，表示序列中整数的个数。
• 第二行输入 n 个整数，表示初始序列。

输出格式

输出一个整数，表示将该序列构造成大顶堆所需的最少交换次数。

输入样例

3
1 2 3

输出样例

1