文昌各个吧 关注:134贴子:15,618
  • 1回复贴,共1

【算法】寻求最大数

取消只看楼主收藏回复

今给定一个数组:寻求里面的最大数,这个最大数必须是由数组中另外两个数相加得到。
比如给定:1,2,3,4.则最大数为4,因为4=1+3
给定1,2,3,6则最大数为3,因为3=1+2,6不行所以不是最大数。
请给出算法和时间复杂度。


1楼2011-10-13 12:31回复
    首先进行排序,可以用合并交换排序法完成,时间复杂度为O(nlogn)
    下一步就是从有序的数组中寻找,最简单的就是一一比较,取最大和次最大相减,看看有没有存在数组中,以此一个个相减,知道找到为止。时间复杂度为O(n^3).显然这个时间太长了。好一点的是O(n^2).大家看看有没有更好的算法。


    2楼2011-10-13 12:45
    回复