최대의 합 연속 부분 배열 (면접 질문)

가능한 중복 : 나는 소프트웨어 엔지니어의 위치에 대한 어도비의 인터뷰에서 오늘 다음과 같은 질문을했다
Find the maximum interval sum in a list of real numbers.최대의 합 연속 부분 배열 (면접 질문)

문제 주어진 배열이 arr[1..n] 인 정수입니다. 최대의 합계를 가지는 배열 내의 연속 한 부분 배열의 합계를 찾아내는 알고리즘을 기술합니다. 모든 숫자가 음수이면 0을 반환합니다.

예

배열 arr[1..6] = [ 12, 14, 0, -4, 61, -39 ]

[ 12, 14, 0, -4, 61 ]로 구성 않음

83 감안할.

나는 O(n logn)에서 실행되는 솔루션을 생각 해낼 수 있었지만 매우 효율적이라고 생각하지 않습니다. 인터뷰 담당자가 O(n) 알고리즘을 작성하라고 요청했습니다. 나는 그걸 생각할 수 없었다.

이 문제에 대한 O(n) 해결책을 작성하는 방법에 대한 의견이 있으십니까? C/C++/Java로 구현되는 알고리즘. 사전에

덕분에

출처

2011-03-21 WebDev

"프로그래밍 진주"이 문제에 대한 전체 장 거기입니다. –

아주 간단한 문제입니다. 양쪽 끝에서 차례로 이동하십시오. 현재 위치로 시작하거나 끝에서 현재 위치까지의 합계가 음수가 될 때까지 각 끝에서 배열을 자르십시오. O (n) –

당신은 O (N)에서 실행 Kadane's algorithm를 사용할 수 있습니다. 추천 읽기 - 여기

은 (뻔뻔 here에서 복사) 알고리즘

Initialize: 
    max_so_far = 0 
    max_ending_here = 0 

Loop for each element of the array 
    (a) max_ending_here = max_ending_here + a[i] 
    (b) if(max_ending_here < 0) 
      max_ending_here = 0 
    (c) if(max_so_far < max_ending_here) 
      max_so_far = max_ending_here 
return max_so_far

출처

2011-03-21 13:34:52

다음은 참조 용 위키 피 디아 문서에 대한 링크입니다 : http://en.wikipedia.org/wiki/Maximum_subarray_problem –

배열에 대한 정보 : [-12, 14, 0, -4, 61, -39] 실제 결과 : [-12, 14, 0, -4, 61] 예상 : [14, 0, -4, 61] –

최대의 합 연속 부분 배열 (면접 질문)

답변

관련 문제