设有 n 个正整数， 分别为 a1,a2......an， 将它们连接一排， 组成一个最大的多为整数， 例如： n=3 时， 3 个整数 13,312,343， 连成的最大整数位 34331213 又如： n=4 是， 4 个整数 7,13,4,246， 连成的最大整数位 7424613 请给出一种最优的数字顺序， 使连成的整数最大， 要求： 1） 给出你的贪心选择策略 2） 证明贪心选择的正确性 3） 写出解决此问题的贪心算法

1. 贪心选择策略：
我们可以采用贪心选择策略，将给定的整数按照组成的数字进行比较排序。具体而言，对于任意两个整数 a 和 b，我们将它们转换为字符串进行比较，如果字符串 a+b 的字典序大于字符串 b+a 的字典序，则认为 a 应该在 b 的前面。

2. 贪心选择的正确性证明：
我们需要证明按照贪心选择策略得到的数字顺序可以组成一个最大的多位整数。假设存在一个更优的排列方式，其中有两个相邻的整数 a 和 b，按照最优顺序排列时，a 在 b 的后面。如果我们发现将 a 和 b 交换位置可以得到一个更大的多位整数，即将 a 放在 b 的后面，那么这个原先被认为是最优的顺序实际上不是最优的，与假设矛盾。因此，按照贪心选择策略得到的数字顺序是最优的。

3. 解决此问题的贪心算法：
1. 输入：n 个正整数的数组 nums[]，大小为 n。
2. 将数组中的整数转换为字符串。
3. 按照字符串的字典序进行降序排序。
4. 将排序后的字符串按顺序连接起来，形成最大的多位整数。
5. 输出连接后的字符串，即为最优的数字顺序。

该贪心算法的时间复杂度为 O(nlogn)，其中 n 是整数的个数。排序操作占据主要的时间开销。贪心算法的正确性在证明中已经说明了。该算法可以得到使连成的整数最大的最优数字顺序。

相关问题

设有 n个正整数 a1 a2 ... an​，将它们连接成一行，相邻数字首尾相接，组成一个最大的整数。 例如：13、312、343 可以组合成为的最大数为 34331213 。 输入数据共两行，第一行有一个整数，表示数字个数 n。第二行有 n 个整数，表示给出的 n 个整数 a1 到 an。

题目大意：有n个整数a1,a2,...,an，将它们连接成一行，相邻数字首尾相接，组成一个最大的整数。例如：13 312 343 可以组合成最大的整数为34331213。输入数据共两行，第一行有一个整数，表示有n个整数；第二行有n个整数，表示n个整数a1到an。

解答：本题的核心是确定两个整数a和b连接后的大小，具体方法是将它们先转换成字符串，然后按照连接后的大小进行比较。转换成字符串后，比较a+b和b+a的大小即可。接下来，我们就可以用sort函数将n个整数进行排序，使得其连接后的数字最大。最后，将排序后的n个数按顺序连接在一起即可。

给定若干个正整数a0、a1 、...、an-1,从中选出若干数,使它们的和恰好为k, 要求找

当给定若干个正整数a0、a1、...、an-1时，我们可以使用动态规划的方法来找出和为k的数。

首先，我们定义一个二维数组dp，其中dp[i][j]表示从前i个正整数中选取若干个数，使其和为j的情况数。

然后，我们初始化dp数组。当只有一个正整数a0时，若a0等于k，则dp[0][k]为1，否则dp[0][k]为0。

接下来，我们根据动态规划的转移方程进行计算。对于正整数ai，对于j大于等于ai，有两种情况：
1. 不选择ai，则此时的情况数为dp[i-1][j]；
2. 选择ai，则此时的情况数为dp[i-1][j-ai]。

因此，dp[i][j]应为以上两种情况的和。

最后，只需返回dp[n-1][k]的值即可，即从n个正整数中选取若干个数，使其和为k的情况数。

注意：以上方法只能找出情况数，不能直接找到具体的数。

以上是一个解法的大致思路，具体实现过程中还可以进行一些优化，例如使用一维数组代替二维数组，节省空间复杂度。实际解决问题时，还需要考虑边界条件和输入数据的合法性。