请问一道题目

anselcat

给定一个正整数数组, A, B, C 都是其中不同的元素, 要求C = A + B, 求出 C 的最大值   给出你的最优算法, 分析时间和空间复杂度

drunkedcat

原帖由 anselcat 于 2008-9-17 17:39 发表
给定一个正整数数组, A, B, C 都是其中不同的元素, 要求C = A + B, 求出 C 的最大值   给出你的最优算法, 分析时间和空间复杂度

问题不够明确：

C 是已知的，又要 C = A + B, 怎么会有“最大值”呢？

ringz

lz的“最大值”的意思应该是数组中满足条件的最大的C

ringz

我的思路是先排序，然后从大到小的判断是否符合条件。
排序复杂度O(nlogn)，判断是否符合条件要O(n^2)。

雨过白鹭洲

算法基本不会

除了O(n^2)。。。

cugb_cat

dp

ps,每次都二分，分别找两边的最大值。。

[ 本帖最后由 cugb_cat 于 2008-9-17 21:24 编辑 ]

Godbach

看来偶要加强算法的学习啊

freearth

将数组由小到大排序，时间O(nlogn);
从最大的数开始考察，直到找到一个满足条件的C：最坏O(n*nlogn)
1：二分查找C－最小的元素； 找到，返回C，否则记录下该元素应该插入的位置M；
2：对于M之前的每一个元素重复1的过程 ;
总的时间代价：O(n*nlogn)

原帖由 anselcat 于 2008-9-17 17:39 发表
给定一个正整数数组, A, B, C 都是其中不同的元素, 要求C = A + B, 求出 C 的最大值   给出你的最优算法, 分析时间和空间复杂度

jinmiaobis

先从小到大排序,假设数组长度为N
d=最大值减第二大值,2分法在剩余数组中找到和d相等的值,返回,没找到,d=最大值减第三大值,2分法在剩余数组中找到和d相等的值,返回,没找到,继续.如果最大值不是c,递归n-1.

ringz

排序以后判断某个最大值是否满足条件，可以优化到O(n)。
首先假设已经完成了从小到大的排序
让A=最小的数,B=第二大的数, C=最大的数，
若A+B=C，输出C；
若A+B<C，A向后移指向次小的数，重复判断；
若A+B>C，B向前移指向次大的数，重复判断；
若A>＝B，C指向次大的数，递归。