总和最多为“k”的子序列
给定一个大小为n的非递减数组a和一个整数k，如何找到数组a的一个子序列S，其元素的最大可能和，使得这个和最多为k。如果有多个这样的子序列，我们只想找到一个。
例如，让数组为{1,2,2,4}，n=4，k=7。那么，答案应该是{1,2,4}。
蛮力方法大约需要O（n（2^n-1））但是有更有效的解决方案吗？
共有1个答案
在一般情况下，答案是否定的。
仅仅决定是否有一个解决方案，其中元素的总和为k，就相当于子集和问题，因此已经NP完全。
子集和问题可以等价地表示为：给定整数或自然数w_1，它们中的任何一个子集是否精确地求和
然而，如果表示最大数w所需的n或P位数较小，则可能有更有效的解决方案（例如，如果P较小，则基于动态规划的伪多项式解）。此外，如果你所有的数字w都是正数，那么也有可能找到更好的解决方案。
-
我需要找到总和大于或等于< code>k的最小子阵列长度。数组将只有正数。 例如 输入:< code>target = 7，< code>nums = [2，3，1，2，4，3]输出:2说明:子数组[4，3]在问题约束下长度最小。 在我的代码中，对于输入:< code>target = 7，< code>nums = [2，3，1，2，4，3]我得到的答案是< code>3，但正确答案是< cod
-
本文向大家介绍C ++中最小K总和最短的子数组，包括了C ++中最小K总和最短的子数组的使用技巧和注意事项，需要的朋友参考一下 假设我们有一个数组A。我们必须找到A的最短，非空，连续子数组的长度，其总和至少为K。如果没有这样的子数组，则返回-1。 因此，如果输入类似于[5,3，-2,2,1]且k = 6，则输出将为2，如我们所见（5 + 3）> = 6 为了解决这个问题，我们将遵循以下步骤- n：
-
我在阅读了允许K个异常的最长递增子序列后创建了这个线程。我意识到提问的人并没有真正理解这个问题，因为他指的是一个链接，该链接解决了“允许一次更改的最长递增子数组”问题。所以他得到的答案实际上与李的问题无关。 假设给定一个长度为N的数组A。查找允许K个异常的最长递增子序列。 示例：N=9，K=1 A=[3,9,4,5,8,6,1,3,7] 答案：7 说明： 最长递增子序列为：3,4,5,8（或6），
-
我最近遇到一个问题如下。
-
在给定的数组中，我试图找到子序列的总数，以便： 连续各学期差额不大于3 子序列的第一个元素是数组的第一个元素 子序列的最后一个元素是数组的最后一个元素 例如，在数组：中，它有5个遵循上述条件的子序列。 我正在尝试一种自下而上的方法。我尝试了以下方法，但它没有给出所有子序列和输出4，而不是5。 我该怎么做？我的直觉是，这种方法可能类似于最长的递增子序列，但不确定如何实现。
-
相关主题： 卡达内算法