최대 원형 서브 러 레이 합계

Question

Jeff Erickson의 책 알고리즘의 질문입니다.

A가 원형 배열이라고 가정합니다. 이 설정에서, "인접한 서브 어레이"는 간격 A [i .. j] 또는 접미사 다음에 접두사 A [i .. n] · [1 .. J] 일 수있다. 가장 큰 합계와의 인접한 소형 배열을 찾는 알고리즘을 기술하고 분석하십시오. 입력 배열은 실수로 구성됩니다.

내 접근 방식 :

두 가지 가능성이 있습니다

1) 포장 없음 (Kadane의 알고리즘을 사용할 수 있음)

2.) 포장 (즉, 서브 어레이의 시작 지수가 끝 인덱스보다 큽니다) (이 경우에는 의심의 여지가 있습니다)

이제 두 가지 경우를 결과로 복귀시킵니다.

두 번째 경우에는 인터넷을 검색하면 증명없이 접근법을 제공합니다.

최소 합계로 Subarray를 찾아 전체 배열의 합계에서 뺄 것입니다 (즉, 합계 (a) - min_subarray_sum (a)). 이 솔루션은 어떻게 정확합니까?

두 번째 케이스에 사용되는 방법에 대한 링크 : https : // www. geeksforgeeks.org/maximum -concefuous-circular-sum/

Answer 1

$ a $ 배열이되도록하자, $ b $ $ \ sum_ {b \ in b} b $ 을 최대화하고 $ C $ $ a $ 이 아닌 에있는 subarray가되어 있습니다.> $ b $ . $ C $ 은 원형의 서브 어레이이기도합니다.

$ \ sum_ {a}} a=sum_ {b \ in b} b + \ sum_ {c} c} c $ $ \ sum_ {c \ in c} c=sum_ {a} a - \ sum_ {b \ in b} b $ 을 의미합니다. $ \ sum_ {a}} a $ 은 상수 (WRT $ b $ )이며 $ B $ $ \ sum_ {b \ in b} b $ , $ C $ $ \ sum_ {c \ in c} c $ .

$ b $ 및 $ C $ 은 원형뿐만 아니라 연속적이므로 $ o (n) $ 시간에 발견 될 수 있습니다.