매일프로그래밍 [실리콘밸리 알고리즘] - 가장 큰 이어지는 원소들의 합??? (18/02/19)

https://mailprogramming.com/

이 곳에서 1주마다 정기적으로 코딩문제를 받고, 풀어보고 있다.

실리콘밸리에서 소프트웨어 엔지니어로 일하고 있는 팀원들로 구성된 팀이라고 한다.



2. 18/02/19

정수 배열(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

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

arr = [-1, 3, -1, 5]


cur_sum = 0

for i in arr:
    cur_sum = max(cur_sum+i, i)

print("Output: " + str(cur_sum))

후기
: 마이크로소프트 코딩테스트 문제라고 한다.
 화이트보드에 리스트를 그리면서, 처음에는 단순히 Start Point를 찾는 알고리즘을 찾기 위해 각 인덱스를 Start Point로 하게 하여, Sum이 가장 큰 값을 찾아나가면 되겠구나라고 생각했지만, 시간복잡도 O(n)을 초과했다.
 CurrentSum이라는 힌트를 보고, cur_sum+i와 이전까지의 합인 cur_sum를 비교해보기도 하고, cur_sum + i > 0라는 조건도 사용해보았지만, 테스트해보니 막상 원하는 결과가 나오지 않았다. 결국 해설을 보고서야 이렇게 될 수 있다는 것을 알았다.

 답을 알고나서는 매우 간단한 거였지만, 알기 전까지는 도저히 아이디어가 떠오르지 않았다 ㅠㅠ..