任意输入一组数列，求出不相邻的两个数和的最大值。新手第高手帮一下

...............................你真厉害.............这么经典啊    ！！！！！！

找出前三大，如果有并列第三大的，那就和没有并列第三大分两种大情况，然后这个题目就能解决了

是不是先用冒泡法找出最大的三个数呀

这个问题无需找前三大吧？？这个问题是跟找最大值有些类似的问题啊！！
---------------------------------------------------------
解题思路：
假设输入的一组数列存放于数组a中，共n个数
最大值max初始为a[0]+a[2]
用个二层循环:
for(i=0;i<n-2;i++)
    for(j=i+2;j<n;j++)
        if(max<a[i]+a[j])max=a[i]+a[j];
则题目要求的最大值就有了啊！      


[ 本帖最后由 jack10141 于 2010-9-9 00:07 编辑 ]

收到的鲜花

• 遮天云 于 2010-09-09 12:54 送鲜花  4朵   附言：妙

楼上的就是高

这个和找前三大的办法的区别是，时间级别上差了一个n
楼主没有说这个n最大多大，那么如果n有10000个，那这个时间差就很巨大了

回帖得分顺便学习下，新手。

不是吧？我还真没有没有考虑过运行时间复杂度的问题。。。
但是要找前三大，你用什么办法找呢？？可否给个代码或者详细解题办法大家参考下？？

[ 本帖最后由 jack10141 于 2010-9-9 18:27 编辑 ]

说到只要知道前几大的数，我写了个代码：
#include <stdio.h>

typedef struct mlist
{
    int n;
    int flag;
}mlist;

int cnt_ml;
mlist ml[20];

void ml_push(int n)
{
    ml[cnt_ml].n = n;
    ml[cnt_ml].flag = 0;
    cnt_ml++;
    while (cnt_ml > 10)
    {
        int nmin = -1, n;
        for (n=0; n<cnt_ml; n++)
        {
            if (ml[n].flag==0 && (nmin == -1 || ml[n].n<ml[nmin].n))
            {
                nmin = n;
            }
        }
        ml[n=nmin].flag = 1;
        while (nmin>0 && ml[nmin-1].flag)
        {
            nmin--;
        }
        while (n<cnt_ml && ml[n].flag)
        {
            n++;
        }
        if(nmin)++nmin;
        for (; n<cnt_ml; ++n, ++nmin)
        {
            ml[nmin] = ml[n];
        }
        cnt_ml = nmin;
    }
}

int main()
{
    int n;
    while (scanf("%d", &n)!=EOF)
    {
        int s, t=0;
        cnt_ml = 0;
        for (; t<n; ++t)
        {
            scanf("%d", &s);
            ml_push(s);
        }
        for (t=0; t<cnt_ml; ++t)
        {
            if (ml[t].flag)
            {
                printf("_ ");
            }
            else
            {
                printf("%d ", ml[t].n);
            }
        }
        puts("");
    }
    return 0;
}
例如，输入：
20
1 23 4 56 7 8 9 10 24 31 2 35 2 33 46 24 41 21 22 1

第一个数表示下一行要输入20个数，
然后程序会输出
56 _ 35 _ 33 46 _ 41 _
下横线表示中间有一串数字忽略掉
这样，就会保留下最大的五个数，并且复杂度是线性的，所用的内存空间也很小，只开了个20的数组
之后再套用那个二重循环的代码，就能以非常快的速度算出答案了
不过不知道这个代码是不是一定对的，但我觉得只要留下前五大就足够了，甚至可能只需要前四大的数，不知道有没有反例呢

收到的鲜花

• 赵本山 于 2010-09-12 16:20 送鲜花  5朵   附言：厉害