최대 서브 어레이

Question

"프로그래밍 진주"열 8에 있습니다. 최대 하위 배열 문제가 있습니다.

문제점 :

입력이 N 부동 소수의 벡터 X이고; 출력은 입력의 인접한 서브 벡터에서 발견되는 최대 합계입니다. 문제 정의를 완성하기 위해, 모든 입력이 음수 일 때 최대 합 서브 벡터는 합계가 0 인 빈 벡터입니다.

가장 효율적인 솔루션 : 우리는 제로, 빈 서브 벡터의 합으로 음수의 배열의 최대 서브 벡터를 정의 :이 칼럼에있는 운동이있다

maxsofar = 0 
maxendinghere = 0 
for i = [0, n) 
    maxendinghere = max(maxendinghere+x[i], 0) 
    maxsofar = max(maxsofar, maxendinghere) 

. 대신 최대 서브 벡터가 가장 큰 요소의 값이되도록 정의했다고 가정합니다.; 다양한 프로그램을 어떻게 바꾸시겠습니까?

나는이 운동에 대한 두 가지 질문이 (1) 나는 가지에 의해 혼동 해요 "우리가 대신 큰 요소의 값으로 최대 서브 벡터를 정의했다고 가정하자." 음수 배열의 최대 서브 벡터가 배열의 가장 큰 요소가된다는 뜻입니까?

예

: 배열 [-1 -2 -3, 최대 서브 벡터 : -1 배열 : [-1 1 2 3], 최대 서브 벡터 : 2 3이 거짓 질문

미안 , 영어는 내 순진한 언어가 아닙니다.

(2) 작성자는 "maxsofar = 0으로 maxsofar = -infinity로 할당 바꾸기"라는 해결책을 제시했습니다. 이 솔루션은 내 질문에 대한 이해를 바탕으로 올바르지 않은 것 같습니다.

예 : 배열 : [-1 -2 -3], 대답은 -1이어야합니다. 그러나 솔루션에 따르면, 0

감사합니다, 나는 당신과 동의

Answer 1

입니다. 저자의 해결책이 maxsofar의 초기화를 변경하는 것이라면 모든 알고리즘에서 변경되지 않습니다.