프로그램의 실행 시간을 Θn으로 만드는 방법

요구 사항은 입력이 -5에서 5까지의 범위로 설정되며, 결과는 정수의 가장 긴 부분 집합을 제공해야합니다. 0보다 크거나 같습니다.프로그램의 실행 시간을 Θn으로 만드는 방법

I 만 다음으로 올 수 입력이 입력 [0 내지 N]

let start, longestStart, end, longestEnd, sum = 0 

for i=0 to n-1 
start = i 
sum = input[i] 
    for j=1 to n 
    if sum + input[j] >= 0 then 
    end=j; 
    if end - start > longestEnd - longestStart then 
    longestStart = start; 
    longestEnd = end;

것이다 그러나 이것은 (n은 2 ^) Θ이다. 나는이 루프가 될 Θ (n)의 우리가 숫자의 배열이 적용 할 수있는 A, B 또는 N에 대한

a - b == (a + n) - (b + n)

때문에 당신에게

출처

2017-02-08 swordgit

감사를 만들 수있는 방법이 무엇인지 알고 싶습니다 모든 요소의 누적 합계를 0에서 현재까지 유지합니다. 위의 방정식에서 인덱스 a에서 b까지의 모든 하위 배열의 합계는 sum (요소 0-b) - sum (요소 0-a)입니다.

로컬 최소값과 최대 값 및 이들의 합계를 추적하면 한 번에 가장 큰 범위의 하위 배열 즉 O (n)을 찾을 수 있습니다.

출처

2017-02-08 02:11:18 Bohemian

감사합니다. 나는 아직도 약간 혼란 스럽다. [1, 2, 3, -5, 4, 3, -1]로 입력이 있고이 배열의 합은 [1, 3, 6, 1, 5, 8, 7]입니다. 전체 배열은 가장 긴 부분 배열이지만, 지역 최소값과 최대 값으로 어떻게 얻을 수 있습니까? – swordgit

@swordgit : 예를 들어 답을 찾고있는 전체 배열이 아닌가? 합이 0보다 크거나 같은 정수의 가장 긴 하위 집합을 요청했습니다. –

프로그램의 실행 시간을 Θn으로 만드는 방법

답변

관련 문제