프로그래밍 면접 문제 3 : Largest Continuous Sum

이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.

이전글 – 프로그래밍 면접 질문 2 : Matrix Region Sum

이 문제는 가장 많이 출제되는 면접 문제 중 하나입니다. 주어진 정수형 배열(양수, 음수 모두 포함)에서 가장 큰 연속 합계를 구하는 문제입니다.

배열 내의 정수가 모두 양수라면, 단순히 모든 숫를 더하면 됩니다. 배열 내의 음수가 있으면 약간 복잡해 집니다. 알고리즘은 수를 더하고 currentSum 변수에 이 값을 저장하는데서 시작합니다. 각 요소를 더한 다음 방금 더한 결과가 현재까지의 최대치보다 더 큰지 확인합니다. currentSum 변수 값이 양수면 계속 진행합니다. currentSum 값이 음수가 되면, 더한 결과 값을 감소시키기 때문에 새로운 currentSum에서 다시 시작합니다. 배열 내의 정수가 모두 음수인 경우를 감안해서 currentSum을 0으로 초기화 하지 말아야 한다는 점에 주의합니다. 이 경우에는 가장 큰 음수가 결과 값이 됩니다. 코드는 상당히 간단하고 명확합니다:

int LargestContinuousSum(int[] array)
{
    int maxSum;
    int currentSum;
    maxSum = currentSum = array[0];

    foreach (int number in array)
    {
        currentSum = Math.Max(currentSum + number, number);
        maxSum = Math.Max(currentSum, maxSum);
    }

    return maxSum;
}

시간 복잡도는 O(N)이고, 공간 복잡도는 O(1)이며, 이는 효율적인 결과입니다.

다음글 – 프로그래밍 면접 질문 4 : Find Missing Element