最大子阵问题如何具有最优子结构？
最大子阵问题如何具有最优子结构？
提问于 2021-07-19 15:48:34
据我所知，您需要一个问题才能有一个适用于动态规划的最优子结构。
我不明白的是。
接受以下数组
A= 1、6、-3、1、5、-1
根据维基百科：
在计算机科学中，如果一个问题的最优解可以由它的子问题的最优解来构造，那么它就被称为具有最优子结构。这个性质被用来确定动态规划和贪婪算法对一个问题的有用性。
我的困惑就在这里。
如果我被要求在上面给出的数组中找到大小为3的最大子数组，答案将是1，5，-1 (总和5)。
但是，如果我要找到大小为2的最大子数组，答案将是(1,6)，它与前面的答案没有共享元素。
我不能理解最优子结构是什么意思，但我不明白是怎么回事。
回答 1
Stack Overflow用户
回答已采纳
发布于 2021-07-20 11:09:33
这里的重叠子问题不是子数组长度，而是包含数组长度。因此，如果F(i:j, s)给出从索引i到索引j的包含(子)数组中长度s的最大值子数组，那么我们可以证明
F(0:k, s) = Max( F(0:k-1, s), F(k-s+1:k, s) )这是重叠的最优子结构。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/68443444
复制相关文章
相似问题
腾讯云开发者
