最大子阵列问题如何具有最佳子结构？
据我了解，您需要一个问题才能有一个适用于动态规划的最佳子结构。
我不明白的是。
采用以下数组
A=[1,6，-3,1,5，-1]
根据维基百科:
在计算机科学中，如果一个问题的最优解可以由其子问题的最优解构造出来，则称该问题具有最优子结构。此属性用于确定动态规划和贪婪算法对某个问题的有用性。
这就是我的困惑所在。
如果让我在上面给出的数组中找到大小为 3 的最大子数组，答案将是 1、5、-1（总和 5）。
但是，如果我要找到大小为2的最大子阵列，答案将是(1，6)，它与前一个答案没有共享元素。
我一定不明白最优子结构意味着什么，但我不知道如何。
共有1个答案
这里重叠的子问题不是子阵列长度，而是包含的阵列长度。因此，如果< code>F(i:j，s)给出从索引< code>i到索引< code>j的包含(子)数组中长度为< code>s的最大值子数组，那么我们可以证明
F(0:k, s) = Max( F(0:k-1, s), F(k-s+1:k, s) )
这是重叠的最佳子结构。
-
** 题目描述 ** 给定K个整数组成的序列{ N1, N2, …, NK}，“连续子列”被定义为{ Ni,Ni+1 , …, Nj}其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。 本题旨在测试各种不同
-
我必须解决一个很像最大子数组问题的问题。我必须找到平均值大于k的最大子数组。我以为下面这招。我可以将大小为n的数组a[]转换为B[]，其中B[I]=a[I]-K。所以现在平均值一定>0。但是平均值大于零并不意味着总和大于零？所以我可以直接应用Kadane的算法。我说的对吗？（总是在有1个正值的约束下）
-
有人能为下面的问题提出一个简单的解决方案吗？ 最长子数组：查找子数组中元素之和小于或等于“k”的最长连续子数组的长度。 输入为:< code>array和< code>k。 例子： 输出： 2个 解释: 子数组：｛1｝，｛2｝，｝3｝，1,2｝，2,3｝，{1,2,3} {1，2} =
-
在长度为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 。
-
给定一个2维正整数数组，求和最大的HxW子矩形。矩形的总和是该矩形中所有元素的总和。 输入：具有正元素的二维数组NxN子矩形的HxW大小 输出：HxW大小的子矩阵，其元素的总和最大。 我已经使用蛮力方法解决了这个问题，但是，我现在正在寻找一个具有更好复杂性的更好的解决方案（我的蛮力法的复杂性是O（n6））。