我正在询问您对这个问题的想法：
I have one array A, with N elements of type double (or alternatively integer). I would like to find an algorithm with complexity less than O(N2) to find:
max A[i] - A[j]
对于 1 abs()。我想到：
- 动态规划
- 二分法，分而治之
- 对跟踪索引进行排序后进行一些处理
您有什么意见或想法吗？您能否指出一些好的参考资料来训练或取得进展以解决此类算法问题？
对阵列进行三遍扫描。首先从j=2向上，填充辅助数组a with minimal到目前为止的元素。然后从上往下扫i=n-1向下，填充（也是从上到下）另一个辅助数组，b, with maximal到目前为止的元素（从顶部）。现在扫描两个辅助数组，寻找最大差异b[i]-a[i].
这就是答案。O(n)总共。你可以说这是一种动态规划算法。
edit:
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
