给定索引约束的最大和子数组
如果某些数组索引不能配对，我将如何找到唯一正整数数组的最大和？
例如，我们有一个数组：[8,2,1,3,9,4]
索引（0,4）和（4,5）处的元素彼此不喜欢。
在这种情况下，最大和为：8 2 1 3 4=18
假设这是100个条目的规模和多达一半的约束，您将如何处理这个问题？
是否有一个像图形这样的数据结构是有用的还是有一些DP？我主要关心的是高效的运行时。
共有1个答案
您试图解决的是最大权重独立集问题。这是图论中的一个问题。
数组索引对应于图的顶点。每个顶点的权重是相应索引处的数组值。在您的示例中，顶点0的权重为8，顶点4的权重为9。
互不相似的数组索引对对应于图的边。例如，顶点0和4之间有一条边。
您正在寻找一组数组索引，其中没有两个索引彼此不喜欢。就图而言，您需要一组顶点，其中没有两个顶点通过边连接。这样一组顶点被称为独立集。
在所有独立集中，您想要顶点权重之和最大的集。这就是最大权重独立集问题。
该问题的蛮力方法尝试n个顶点的所有2个子集，以确定最大权重。不幸的是，这个问题是NP难的。人们认为NP难问题不能在多项式时间内求解。换句话说，你不可能比暴力手段做得更好。
-
给定一个正整数数组，返回最大和。 只有一个限制：如果你选择两个连续的元素，你不允许在你的总数中添加任何后续的元素，你的总和是到那个点为止的累积量。你的目标是最大化你的总和。 输入：[1,4,2,10] 产出：14 输入：[1,4,5,3] 产出：9 我在第一个测试案例中一直失败。我尝试了DP解决方案，但产生了相同的结果？任何帮助都将不胜感激。
-
本节将讨论SQL constraints 和指标。在SQLAlchemy中，键类包括 ForeignKeyConstraint 和 Index . 定义外键 A 外键 在SQL中是一个表级构造，它约束该表中的一个或多个列，使其只允许存在于不同的列集中的值，通常但不总是位于不同的表中。我们称之为约束 外键 列和它们被约束到的列 引用的 柱。被引用的列几乎总是为其所属表定义主键，尽管有例外。外键是连接
-
最近在一次工作面试中，我被要求在给定约束条件下求两个数组的最大和。这个问题措辞不同，但归结起来就是我上面所说的。没有提到元素是不同的，或者数组是被排序的。 例子： 请注意，由于约束，这与在2个数组中查找第k个最大和的对不同。 一个蛮力解是取2个数组的笛卡尔积，计算每对的和，过滤掉大于7000的，排序，取相等的顶值，时间复杂度为O（n2），我们能做的更好吗？
-
这个问题有多项式解吗？如果有，你能呈现吗？
-
想改进这个问题吗？更新问题，让它只通过编辑这篇文章来关注一个问题。 给出了一个由N个整数组成的零索引数组A。此数组的平衡指数是任意整数P，因此0≤ P 例如，考虑以下由N = 8个元素组成的数组A: P = 1是这个数组的平衡指数，因为: P=3是该数组的平衡指数，因为： P = 7也是一个均衡指数，因为： 并且没有索引大于7的元素。 P = 8 不是均衡指数，因为它不满足条件 0 ≤ P 现在我