1912

문제풀이

n개의 정수 배열에서 1개이상의 연속된 수를 선택해서 구할 수 있는 가장 큰 합 구하기

입력

• 정수 n
• n개의 정수로 이루어진 수열

로직

• 풀이1. 1개만 선택한 경우의 최대값을 구한다음 0보다 큰 경우만 누적하면서 최대값을 갱신한다.
• 풀이2. 첫번째 값을 기본값으로 두고 1개만 선택한 경우의 이전값과 더한 값 중 더 큰 값을 선택한다.

맞왜틀

• 오답: 1개만 선택한 원본배열을 제외하고 최대값을 구하려고 해서 틀림
• 메모리 초과: 모든 누적 합을 배열에 구해서 틀림
• 시간 초과: 모든 누적 합을 이중 반복문으로 구해서 틀림

답안 비교 및 리팩토링

• O(n)으로 해결 가능한 문제이다.