가장 긴 연속 서브 시퀀스 알고리즘

Question

아래와 같이 "오프셋"및 "길이"속성을 가진 "범위"개체의 ​​배열이 있습니다. 오름차순으로 "오프셋"으로 정렬한다고 가정합니다.

범위 배열은 포함이 경우

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

간단한 선형 알고리즘 (파이썬, 나는 코드가 개선 될 수있다 확신) : 자바

# 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

{선형 시간이 솔루션은 더 동적 프로그래밍이 필요하지 않습니다. 가장 가까운 문제는
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; 
}