最大子阵变异
我必须解决一个很像最大子数组问题的问题。我必须找到平均值大于k的最大子数组。我以为下面这招。我可以将大小为n的数组a[]转换为B[]，其中B[I]=a[I]-K。所以现在平均值一定>0。但是平均值大于零并不意味着总和大于零？所以我可以直接应用Kadane的算法。我说的对吗？（总是在有1个正值的约束下）
共有1个答案
不，Kadane的算法仍然会给你找到和最大的子数组...我必须解决同样的问题。到目前为止，我发现，如果我们像上面提到的那样创建数组B，然后使数组C包含数组B的部分和，那么我们所寻找的最大间隔（i,j）对于i和j具有相同的数！！！例如：
数组A是：1 10-1-1 4-1 7 2 8 1......给定的k是5，那么数组B是：-4 5-6-6-1-6 2-3 3-4数组C是：-4 1-5-11-12-18-16-19-16-20所以我们要找的子数组是[7,2,8]，长度是3，第一个和最后一个元素是-16！！！！
编辑：我忘了说我们正在搜索一个O(n)或O(n*logn)算法....@lets_solve_it你是对的，但是你的算法是O(n^2)whitch对于我们想要处理的数据来说是很大的。我接近于用C++中的函数映射来解决它，whitch类似于哈希表。我认为这是正确的diredation因为这里数组C的元素与它们的索引有直接的关系！我们的教授还告诉我们，另一个可能的解决方案，是再次使数组C,然后采取a（特殊？）但是我并不完全理解我们期望quicksort做什么。
-
在长度为N的数组中求和最大的邻接子数组。 输入格式： 输出格式： 返回一个整数，表示相邻子数组的最大可能和。 制约因素： 输入2:A=[-2,1,-3,4,-1,2,1,-5,4] 产出2：6 说明2：子数组[4,-1,2,1]的最大可能和为6。 你能告诉我为什么下面的代码不起作用，代码中的错误是什么吗：
-
所以，我刚刚进行了一次在线编程评估，给了我两个问题，其中一个是这个连续的子数组和提供了两个复杂的编码问题+8个MCQ，并将在1小时内完成。 这里我将讨论上面提到的子数组的最大邻接和之一。通常，我发现困难的部分是处理负数和连续。我所做的是首先将应用到给定的数组，然后再次按照负值的绝对值排序，就像i的例如，对于给定的随机数组，我在每个i和所有j迭代后都有一个max，如果max 。
-
我们大多数人都熟悉最大和子数组问题。我遇到了这个问题的一个变体，它要求程序员输出所有子数组和的最大值模某个数m。 设M=13。在这种情况下，子数组6 6（或12或6 6 11 15或11 15 12）将产生最大和(=12)。
-
给定一个2维正整数数组，求和最大的HxW子矩形。矩形的总和是该矩形中所有元素的总和。 输入：具有正元素的二维数组NxN子矩形的HxW大小 输出：HxW大小的子矩阵，其元素的总和最大。 我已经使用蛮力方法解决了这个问题，但是，我现在正在寻找一个具有更好复杂性的更好的解决方案（我的蛮力法的复杂性是O（n6））。
-
我有一个大的NxN位数组，有K个1(其他都是0)。所有非零点的坐标都是已知的——换句话说，这个n×n数组可以表示为K对数组，每个数组包含一个非零点的x和y坐标。 给定一个HxW大小的子矩阵，我需要将其放在我的原始NxN数组上，使其覆盖大多数非零点。 输入：子矩阵的高度H和宽度W 输出：HxW子数组的x和y协弦，其内部有最多的协弦 之前也回答过类似的问题：2D矩阵中尺寸为HxW的最大子阵列，但在我的
-
在一本书（算法导论，但我不记得是哪一章）中，我学到了求解两元素间最大差值问题： 两个元素之间的最大差，使得较大的元素出现在较小的数之后。 查找数组（至少包含一个数字）中和最大的相邻子数组。 例如，给定数组[-2,1,-3,4,-1,2,1,-5,4]，相邻子数组[4,-1,2,1]的最大和=6。 为了解决的两元素间最大差异问题，可以将其转化为数组的最大子数组问题： 我在想为什么。