Алгоритм самой длинной непрерывной подпоследовательности

Question

У меня есть массив объектов «Range» со свойствами «Offset» и «Length», как показано ниже. Предположим, что он будет отсортирован по возрастанию "Смещение".

Массив диапазона содержит:

Offset        Length     Index
-------       -------    -------
100           10         0
110           2          1 
112           5          2
117           3          3
300           5          4
305           5          5 
400           5          6
405           10         7
415           2          8
417           4          9
421           7          10
428           1          11 
429           6          12  
500           4          13
504           9          14

Смежные подпоследовательности в этом случае будут:

Sequence #1 indices: 0, 1, 2, 3
Sequence #2 indices: 4, 5
Sequence #3 indices: 6, 7, 8, 9, 10, 11, 12  <-- (longest!!)
Sequence #4 indices: 13, 14

Предположим, что будет только одна самая длинная последовательность. Итерируя по элементам, я думал создать новый массив для каждой смежной последовательности и вернуть самый большой массив, но это кажется неоптимальным. Есть лучший способ сделать это? Я внедряю в C # 2.0. Функция должна либо возвращать массив, содержащий элементы самой длинной подпоследовательности, либо начальный и конечный индексы самой длинной подпоследовательности в исходном массиве.

Спасибо всем за то, что сделали удар.

Answer 1

Эта проблема не связана с проблемой смежных подпоследовательностей и т. Д., Но является простой проблемой, которая может быть решена за O (n) времени. Мне кажется, что «строки», представленные массивом, не перекрываются, поэтому существует очень простой алгоритм: поместите левый указательный палец в первую строку, а затем проведите правым указательным пальцем вниз, пока вы находитесь в смежных последовательность. Когда последовательность заканчивается, сохраните длину и начальное местоположение. Тогда повторите это. Всякий раз, когда вы найдете более длинную последовательность, чем предыдущая запись, вы обновляете начальное местоположение.

Answer 2

Простой линейный алгоритм (Python, я уверен, код можно улучшить):

# Your array
arr = [
  (100, 10), (110, 2), (112, 5), (117, 3), (300, 5), (305, 5), (400, 5), 
  (405, 10), (415, 2), (417, 4), (421, 7), (428, 1), (429, 6), (500, 4),
  (504, 9)
]

# Where does each element end?
ends = map(sum, arr)

s, e = 0, 0 # start and end of longest contiguous subseq
cur = 0     # length of current contiguous subseq
for j, i in enumerate(range(1, len(arr))):
    # See if current element is contiguous with the previous one
    if (arr[i][0] == ends[j]):
        cur += 1
    elif cur > 0:
        # If not, we may have found the end of a (currently) longest subseq
        if cur > (e - s):
            e = j
            s = e - cur

        cur = 0  # reset subseq length

# The longest contiguous subseq may be at the end of the array
if cur > (e - s):
    e = j + 1
    s = e - cur

# print the start and end index of the longest contiguous subseq
print(s, e)

Answer 3

{Линейное время решения в Java, динамическое программирование не требуется. Самая близкая проблема:
Самая длинная возрастающая подпоследовательность, которая требует O(N^2) DP решения.

int LongestContiguousIncreasingSubsequence(int[] a)     
{

   int maxL = 1,currentL=1;
   int n=a.length;

   for ( int i = 0; i < n-1; i++ )
   {
       if(a[i+1]>a[i])
           currentL++;
       else 
       {
           if (currentL>maxL)
               maxL=currentL;
           currentL=1;
       }               
   }       

   return maxL;
}