【C# 每日一题2】求最长等差数列,该如何解决

【C# 每日一题2】求最长等差数列

题目需求：
在一个升序排列好的数列里面找到最长的等差数列

例子：1 3 5 6 8 9 10 12 13 14
子数列有(两项的不在列举）
1 3 5
1 5 9 13
3 6 9 12
3 8 13
5 9 13
.....

得出的最长的等差数列应该是：6 8 10 12 14

大家各抒己见，踊跃发言，写一下自己的想法吧！

每日一题1 得到了版主的推荐，我们有了一个不错的开始，希望大家都加入进来，一起讨论，共同进步！！

------解决方案--------------------
计算机吗，当然是穷举了，
for (int i = 0; i < length; i++)
{
for (int j = 0; j < length; j++)
{
//根据i，j下标取出两个数，假设就是等差数列的前两位，那么接着再求后面的。
//如果优化，可以记下等差的差值，如果发现这个差值已经处理过，那直接就可以跳过
}
}
------解决方案--------------------

C/C++ code


#include "stdio.h"
#include <map>
using namespace std;

#define MAX_LEN 1000
int data[MAX_LEN];
int length;
int best;
int bestdelta;
int beststart;

void Run()
{
    map<int,int> alldata;
    map<int,int> useddelta;
    scanf("%d",&length);
    for(int i = 0;i < length;i++)
    {
        scanf("%d",data+i);
        alldata[data[i]] = 0;
    }

    if(length == 1)
    {
        printf("%d\n",data[0]);
        return;
    }

    best = 2;
    bestdelta = data[1]-data[0];
    beststart = data[0];
    for(int i = 0;i < length-best+1;i++)
    {
        useddelta.clear();
        for(int j = 0;j <= i;j++)useddelta[data[i]-data[j]] = 0;
        for(int j = i+1;j < length-best+2;j++)
        {
            if(useddelta.find(data[j]-data[i]) != useddelta.end())continue;
            int delta = data[j]-data[i];
            int curlen = 2;
            int curdata = data[j];
            while(true)
            {
                if(alldata.find(curdata+delta) != alldata.end())
                {
                    curlen++;
                    curdata += delta;
                }
                else break;
            }
            if(curlen > best)
            {
                best = curlen;
                bestdelta = delta;
                beststart = data[i];
            }
        }
    }
    for(int i = 0;i < best-1;i++,beststart += bestdelta)printf("%d ",beststart);
    printf("%d\n",beststart);
}


int main()
{
    Run();
    return 0;
}

------解决方案--------------------

C# code


        static void Main(string[] args)
        {
            List<NumListHeader> allList = new List<NumListHeader>();
            string[] s = Console.ReadLine().Split(' ');
            NumListBody max = null;
            int[] allNum = s.ToList().ConvertAll<int>((x) => { return int.Parse(x); }).ToArray();
            allNum.ToList().ForEach((n)=>{

                allList.ForEach((l) => {
                    bool newlist = l.bodys.Count==0;
                    l.bodys.ForEach((b) => {
                        if (n == b.Step * b.length + l.Start)
                        {
                            b.length++;
                            if (max == null || b.length > max.length)
                            {
                                max = b;
                            }
                        }
                        else if (n > b.Step * b.length + l.Start)
                        {
                            l.bodys.Remove(b);
                        }
                        else
                        {
                            newlist = true;
                        }
                    });
                    if (newlist)
                    {
                        l.bodys.Add(new NumListBody() { length =2, Step = n-l.Start, Start = l.Start  });
                    }
                });
                allList.Add(new NumListHeader() { Start = n });
            });
            Console.WriteLine("start:{0},step:{1},length:{2}", max.Start, max.Step, max.length);
            Console.Read();
        }
    }
    class NumListBody
    {
        public int Start;
        public int Step;
        public int length;
    }
    class NumListHeader
    {
        public NumListHeader()
        {
            bodys = new List<NumListBody>();
        }
        public int Start;
        public List<NumListBody> bodys;
    }

【C# 每日一题2】求最长等差数列,该如何解决

相关推荐