首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >在数组中,找到一个优化的算法来求最长子阵的长度之和,而当前元素在子阵中是最高的。

问在数组中,找到一个优化的算法来求最长子阵的长度之和,而当前元素在子阵中是最高的。
EN

Stack Overflow用户
提问于 2020-10-06 00:21:18
回答 2查看 97关注 0票数 0

我有一个类似于这个1,3,5的数组。对于每一个元素,我需要找到最长的子数组,其中当前元素是最高的。答案是所有子数组的长度之和。

解释一下。

索引-0:元素1 ->最长子数组,元素小于当前元素=1

索引-1:元素3 ->最长子阵,元素小于当前元素= 1,3

索引-2:元素5 ->最长子阵,元素小于当前元素= 1,3,5

最终答案=1+2+3=6个子阵列长度

对于这个问题,我能想出一个蛮力O(N ^ 2)。有没有更好的方法来解决这个问题?

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2020-10-06 03:32:51

我给你两个提示。

提示1:具有时间复杂度和空间复杂度O(n)的解决方案是可能的,n是给定数组Arr中的元素数。dynamic-programming标记使头脑坚持它,而不是探索其他可能的解决方案。

现在就在这里停下来,自己试一试,然后再继续阅读。

。

。

。

。

避免无意中让你读到第二条暗示

。

。

。

。

提示2:使用单调堆栈。

现在就在这里停下来,自己试一试,然后再继续阅读。

我喜欢解决这个问题,谢谢!下面的解决方案是直截了当的,只为堆栈.使用空间。

我将向您展示一个模拟,而不是给出一个规则样式的逐行算法。

代码语言:javascript
复制
Index:  0   1   2   3   4   5   
Arr:    44  91  58  54  7   38  

​

​

上给出的解决方案是否正确?

​

​

长度之和= 17,所以,我们有一个正确的解。

后续问题:如果中存在重复的解决方案,会工作吗?如果没有,您将对上述算法进行哪些更改以使其工作?提示:玩>,<,=会有帮助吗?

票数 1
EN

Stack Overflow用户

发布于 2020-10-06 11:25:36

只需在两个方向记录下一大元素的索引,并查找每个元素。O(n)空间和时间

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/64217739

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档