버그 해결을 위한 모든 질문을 던져
0 votes
271 views

알고리즘 공부를 하다가 유명한 문제라고 해서 보다가 

의문점이 생겨 문의드립니다.

 

1차원 배열에서 연속된 부분 구간 중 그 합이 최대인 구간을 찾는 문제

예) 배열 [-7, 4, -3, 6, 3, -8, 3, 4] 에서 최대 합을 갖는 부분 구간은 [4, -3, 6, 3] 으로 합은 10 이다


이 문제를 푸는 알고리즘 중 시간 복잡도가 O(N)인 방법으로 아래의 함수가 있습니다.

 

private int fasttestMaxSum(int[] arr) {

    int N = arr.length;

    int ret = 0;

    int psum = 0;

    for (int i = 0; i < N; i++) {

        psum = Math.max(psum, 0) + arr[i];

        ret = Math.max(psum, ret);

    }

    return ret;

}

 

그런데 배열의 모든 수가 음수인 경우에는 잘못된 값이 나오는데 (최대합의 값이 0)

그렇다면 문제가 잘못된건지, 알고리즘에 문제가 있는건지 궁금합니다.
 

 

[코드 출저] https://androidyongyong.tistory.com/7



 

asked (8 point) , 271 views

2 answers

0 votes
ret 변수의 Math.Max부분에서 0이 최대값으로 잡혀지니 합해봐야 0이되는게아닌지요? 이후로는 어차피 진행되어봐야 0인거같네요.

음수만을 지정한다면 minvalue정도로 초기화하는게 나을거같은데요..
answered (4 point)
0 votes

C#유저라 C#스타일로 적었습니다

 

private int fasttestMaxSum(int[] arr) {

    int N = arr.Length;

    int ret = 0;

    int psum = 0;

    int max = int.MinValue;

    for (int i = 0; i < N; i++) {

        psum = Math.Max(psum, 0) + arr[i];

        ret = Math.Max(psum, ret);

        max = Math.Max(max, arr[i]);

    }

    return 0 > max ? max : ret;

}

answered (14 point)
수정됨

버그 해결을 위해 도움을 구하고, 도움을 주세요. 우리는 그렇게 발전합니다.

throw bug 는 프로그래밍에 대한 전분야를 다룹니다. 질문,논의거리,팁,정보공유 모든 것이 가능합니다. 프로그래밍과 관련이 없는 내용은 환영받지 못합니다.

221 질문
346 answers
356 댓글
375 users