배열의 요소의 최대 합계를 찾습니다. 정수 값의 배열 (음의 정수 포함)을 사용하여 배열의 연속 요소의 최대 합계를 찾는 프로그램을 작성하십시오.

예 :

가

2, 3, -2, -1, 2, -1, 6, 4, -8, 8

가

을 준다 11

나는 faste 인 해결책을 찾고있다. r보다 O (N^2). 내가 Kadane's Algorithm 생각

출처

2012-09-09 user1106337

1,2,5,6은 연속적이지 않습니다. 취할 수있는 부분 집합에 대한 제한이 없다면, 이것은 NP-Complete 문제인 Subset-Sum 문제이지만, 그렇다고는 생각하지 않습니다. – amit

오해를해서 죄송합니다. 나는 설명과 예에서 실수를 범했습니다. :) 둘 다 업데이트했습니다. – user1106337

선형 스캔을 통해이 문제를 해결할 수 있습니다. 합계를 계산하면 현재 최대 값과 합계가 0보다 작 으면 합계를 0으로 재설정하고 계속 진행합니다. 이 탐욕스러운 해결책은 올바른 것으로 입증되었습니다. kadane 알고리즘이라고합니다. http://en.wikipedia.org/wiki/Maximum_subarray_problem – nhahtdh

당신이 실제로 내가 (데이터 구조 및 알고리즘 마크 앨런 와이즈하여 C에서) ... 그것은 매우 아름답고 우아한 해결책 및 해결할 수있는 문제입니다 대학에서 공부 교과서 문제

출처

2012-09-09 13:12:08 Qyrus

링크가 더 이상 유효하지 않습니다 – fayyazkl

를 원하는 것입니다 O (N)에

int MaxSubsequenceSum(int A[]) 
{ 
    int sum = 0, maxSum = 0; 

    for (int j = 0; j < A.Length; j++) 
    { 
     sum = sum + A[j]; 

     if (sum > maxSum) 
      maxSum = sum ; 
     else if (sum < 0) 
      sum = 0; 
    } 
    return maxSum; 
}

출처

2012-09-09 14:08:08

귀하의 게시물은 익명의 사용자가 편집 한 다음 승인되었습니다. 이러한 변화가 실제로 긍정적인지 확인할 수 있습니까? 그것은 논리를 크게 바꾼 것처럼 보였다. – Gray

아니, 나는 그것을 승인하지 않았고 크게 대답을 향상 시키지도 못했다. 나는 그것이 포인트를 위해 완료되었다라고 생각한다 –

익명의 사용자에 의해하게되었다. 그래서 어떤 대리인도 수여되지 않았다. 부담없이 돌아 가세요. 그들은 왜 그것을했는지에 대한 주석을 남겼습니다 (http://stackoverflow.com/posts/12339772/revisions). – Gray

-1

는 먼저 내림차순으로 소정의 배열을 정렬 할 수 있으며, 다음에 의해 배열의 첫 번째 세 개의 요소들을 요약 다음 sum=0 인쇄 합 intializing 의해 sum=arr[0]+arr[1]+arr[2] .

출처

2014-06-12 20:14:35 bitsk

배열의 요소의 최대 합계를 찾습니다. 정수 값의 배열 (음의 정수 포함)을 사용하여 배열의 연속 요소의 최대 합계를 찾는 프로그램을 작성하십시오.

답변

관련 문제