Найдите самую длинную последовательность в списке<int>

Question

У меня есть следующий список:

List<int> days = new List<int> { 1, 4, 5, 6, 7, 8, 20, 24, 25, 26, 30 };

Я хочу получить начальные и конечные числа самой длинной последовательности. Для приведенного выше примера я должен получить (4, 8). Если доступны две последовательности одинаковой длины, я хочу первую.

Примечание: в списке всегда будут номера в порядке возрастания.

пока я пробовал это:

List<Tuple<int, int>> seqs = new List<Tuple<int, int>>();
int _start = 0;
for (int i = 0; i <= days.Count; i++)
{
    if (i == 0)
    {
        _start = days[i];
        continue;
    }

    if (i < days.Count)
    {
        if (days[i] == days[i - 1] + 1)
            continue;
        else
        {
            seqs.Add(new Tuple<int, int>(_start, days[i - 1]));
            _start = days[i];
        }
    }
    else
    {
        seqs.Add(new Tuple<int, int>(_start, days[i - 1]));
    }
}

var largestSeq = seqs
      .OrderByDescending(s => s.Item2 - s.Item1)
      .FirstOrDefault();

Answer 1

Это решение короче, но использует побочный эффект, поэтому его нельзя распараллелить:

var days = new List<int> { 1, 4, 5, 6, 7, 8, 20, 24, 25, 26, 30 };

var groupNumber = 0;
var longestGroup = days
    .Select((x, i) => new
                        {
                            Item = x,
                            Index = i
                        })
    .GroupBy(x => x.Index == 0 || x.Item - days[x.Index - 1] == 1
        ? groupNumber :
        ++groupNumber)
    .OrderByDescending(x => x.Count())
    .First()
    .Select(x => x.Item)
    .ToArray();

Console.WriteLine(longestGroup.First()+", "+longestGroup.Last());

выход:

4, 8

эта версия не использует побочный эффект:

var days = new List<int> { 1, 4, 5, 6, 7, 8, 20, 24, 25, 26, 30 };

var groupEnds = days
    .Select((x, i) => new
    {
        Item = x,
        Index = i
    })
    .Where(x => x.Index > 0)
    .Where(x => x.Item - days[x.Index - 1] > 1)
    .Select(x => x.Index)
    .Concat(new[]{days.Count})
    .ToArray();

var groupBounds =
    new[]{new{First=0,Last=groupEnds[0]-1}}
    .Concat(groupEnds
        .Select((x,i) => new{Item=x,Index=i})
        .Where(x => x.Index > 0)
        .Select(x => new{First=groupEnds[x.Index-1],Last=x.Item-1})
        )
    .ToArray();

var longestGroup = groupBounds
    .OrderByDescending(x => x.Last - x.First)
    .First();

Console.WriteLine(days[longestGroup.First] + ", " + days[longestGroup.Last]);

выход:

4, 8

Answer 2

Моя версия, которая выглядит очень похоже на @Gurgadurgen's.

List<int> days = new List<int> { 1, 4, 5, 6, 7, 8, 20, 24, 25, 26, 30 };           

int longestSequenceLength = 0;
int startIndexOfLongestSequence = 0;
int currentSequenceLength = 0;
int currentStartSequenceIndex = 0;

for (int i = 0; i < days.Count; i++) {
    if (i == 0 || days[i] != days[i - 1] + 1) {
        currentSequenceLength = 1;
        currentStartSequenceIndex = i;
    }
    else {
        currentSequenceLength++;
    }

    if (currentSequenceLength > longestSequenceLength) {
        longestSequenceLength = currentSequenceLength;
        startIndexOfLongestSequence = currentStartSequenceIndex;
    }
}

Console.WriteLine(string.Join(",",days.Skip(startIndexOfLongestSequence)
   .Take(longestSequenceLength))); 

Answer 3

int longestSeqStart = days[0];
int longestSeqEnd = days[0];
int curSeqStart = days[0];
int curSeqEnd = days[0];
int lastVal = days[0];
for(int i = 1; i < days.Count(); i++)
{
    if(days[i] == lastVal + 1)
    {
        curSeqEnd = days[i];
        if(curSeqEnd - curSeqStart > longestSeqEnd - longestSeqStart )
        {
            longestSeqStart = curSeqStart;
            longestSeqEnd = curSeqEnd;
        }
    }
    else
    {
        curSeqStart = curSeqEnd = days[i];
    }
    lastVal = days[i];
}

Я не проверял это, но я смотрел на это в течение хороших пяти минут, и это кажется довольно звуковым. Я пойду запустить некоторые тесты в ideone и вернусь, чтобы отредактировать их в: P

[РЕДАКТИРОВАТЬ] Проверено, и это действительно работает. Для списка целых чисел, "дни"

{1,2,3,4,5,12,13,14,15,16,17,18,2,3,4,5}

Он выплевывает 12-18, что является правильным ответом. Я просто выложу ссылку на Ideone здесь.

[РЕДАКТИРОВАТЬ 2] Обратите внимание, что это едва оптимизировано, и может (и должно) быть передано вниз, прежде чем использовать в реальном коде. Например, я понял только после написания этого, что lastVal на самом деле даже не нужен, так как мы можем просто проверить значение "days" в последнем индексе (i-1).

Это должно служить только логической основой для решения проблемы, которая у вас есть, здесь. Не как окончательное решение.