매일프로그래밍 코딩 테스트#1

1.문제

정수 배열(int array)가 주어지면 가장 큰 이어지는 원소들의 합을 구하시오. 단, 시간복잡도는 O(n).

예제}

Input: [-1, 3, -1, 5]

Output: 7 // 3 + (-1) + 5

Input: [-5, -3, -1]

Output: -1 // -1

Input: [2, 4, -2, -3, 8]

Output: 9 // 2 + 4 + (-2) + (-3) + 8

2.풀이

#매일프로그래밍 코딩 테스트 #1
# 정수 배열(int array)가 주어지면 가장 큰 이어지는 원소들의 합을 구하시오. 단, 시간복잡도는 O(n).
def sumDivisor(arr):
    maxSum = arr[0]
    currentSum = arr[0]
    for i in range(1,len(arr)):
        currentSum = max(currentSum + arr[i], arr[i])
        maxSum = max(currentSum, maxSum)
        print("maxSum의 변화 :%d" % maxSum)
        print("currentSum 변화 :%d" % currentSum)
    return maxSum

# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(sumDivisor([-1,3,-1,5]))
print(sumDivisor([-5, -3, -1]))
print(sumDivisor([2, 4, -2, -3, -5]))

3.discussion

처음에는 currentSum 변수 하나로 문제를 해결할 수 있을 줄 알았다. 그러나 currentSum 값이 작아질 수 있는 경우가 발생하기때문에(이후에 오는 값이 음수이고 합이 음수가 될 경우, 테스트3번경우) currentSum의 최대값을 저장하는 MaxSum변수가 필요하다.