求给定整数集的最大完美子集的大小
给出不同整数的列表
我的想法:< br >一种简单的方法是一个接一个地选择一个元素，看看它形成的完美子集的大小，然后我们可以简单地返回最大值。这将是计算密集型的。< br >有什么好的解决方案吗
共有1个答案
这听起来像是最长增长子序列问题的变体。
您可以在数组Nums[1..N]中按升序对初始数字序列（或集合）进行排序。设L[i]是以位置i处的值结束的最大完美子集的大小（即Nums[i]）。
那么L[i] = L[j] 1如果我们能找到一个指数j使得Nums[j]^2 = Nums[i]。否则，L[i] = 1。因为Nums是排序的，你可以二分搜索法索引j
这给出了一个 O（N log N） 解决方案。
-
我想从数组的一部分找到最大值和最小值。我知道我可以通过复制数组将所需的数组部分复制到另一个数组中，但只是想知道是否可以不复制数组，因为我必须为不同的子数组进行循环 例如： 现在我想从1到4找到子数组的最小/最大值（如果可能，不复制子数组）
-
给定一个数组形式的未排序（多）整数集，求其和大于或等于常量整数x的最小基数子集。 我们的集合是{4 5 8 10 10}，x=15，所以最小基数子集和 这个问题与以下问题相关但不同：给定一个n个整数的列表，找到大于X的最小子集和在前面的问题中，作者要求得到一个和最接近X的子集，这里我们想要任何子集
-
我只能想到一个朴素的算法，它列出集合的所有子集，并检查子集的和是否和是否最小，但它是一个指数算法，列出所有子集需要O(2^n)。我能用动态规划在多项式时间内求解吗？
-
我有这个问题来自hackerearth 给定一个N个整数的数组，C个卡和S个和。每一张卡片都可以用来将给定数组中的一个整数递增或递减1。查找给定数组中是否有任何子集（在使用任意数量的卡之后/之前）具有和S。 输入格式 输出格式 如果存在具有给定和的子集，则打印TRUE，否则打印false。 所以这基本上是子集和问题的一种变体，但我们不是要找出一个给定的具有和的子集是否存在，而是要找到从序列到中最大
-
我有一个包含一些整数值的数组，我需要得到其中的一个子集，它给我的最大和小于给定值 假设我有一个数组： 我想得到这个数组的一个子集，最大化总和，但低于用户给定的限制，比如250。在这种情况下，它应该返回[139,40,29]<我看了一下这个问题和相关的答案，并尝试使用给出的代码，但我不太理解。无论如何，我已经尝试过了，将最小值设置为0，将最大值设置为给定的限制，但它总是返回“5”，这是不正确的，因为
-
我在Scala中做了一个问题，这是任务语句的摘要： 上述示例的输出: 1 2 3 -1 第一行是数组长度，第二行是整数数组(0 以下是我尝试的：选择的元素并不重要。所以我先对给定整数的列表排序最大。然后我选择了第一个元素，检查它是否大于S，如果不大于S，我也选择了第二个元素，依此类推，直到总和大于或等于S。 我的代码（Scala）：