`
mars914
  • 浏览: 432809 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

算法-动态规划:一个数组a[0...n-1],求a[j]-a[i]的最大值,其中i<j

阅读更多

其中数组a[n]是无序的,求a[j]-a[i]的最大值,且i<j,解此题有两种算法:

 

第一种方法:

 

从左往右求下标0到 k - 1 的最小值MIN
从右往左求 下标k到n -1 的最大值MAX

对于每个k都有一个MAX - MIN的值,最后求这个值的最大值即可。

例如数组:4 5 2 6 3 1

K:1 2 3 4 5

MIN: 4 4 2 2 2

MAX:6 6 6 3 1

MAX - MIN,最大的值为6 - 2 = 4, 即为结果

 

第二种方法:

令b[j] = a[j + 1] - a[j],

那么a[j] - a[i]=(a[i+1]-a[i])+(a[i+2]-a[i+1])+...+(a[j]-a[i-1])

                   = b[i] +b[i+1]+ ...+ b[j - 1],

即将问题转化成求一个数组子序列的最大值。这个过程的算法是有O(n)的算法的。

 

-----------------------------------------------

代码实现稍后补上,今天不想写了......

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics