[백준] 1912 연속합 파이썬

링크 : www.acmicpc.net/problem/1912

 

처음엔 쉬운줄 알고, 완전탐색 알고리즘으로 O(N^2)의 시간을 알고리즘을 짰더니 타임아웃 에러로 안 됐었습니다.

 

다 풀고나서 보니 알고리즘도 썩 좋지 않네요 ㅎㅎ

 

(타임아웃 난 코드)

N = int(input())
data_list = list(map(int, input().split()))[:N]
sum_list = list()
for i in range(N):
    max_sum = data_list[i]
    for j in range(1, N):
        if max_sum < sum(data_list[i:i+j]):
            max_sum = sum(data_list[i:i + j])
    sum_list.append(max_sum)

print(max(sum_list))

 

푸는 방법은 다음과 같습니다.

 

1. 먼저 입력을 받습니다.

 

2. 부분 합을 구하는 알고리즘은 풀다가 몰라서 나동빈님의 해설을 참고하였습니다.

 

[참고 : www.youtube.com/watch?v=OxsZKLfaWX0 ]

 

3. 현재 합을 계속 더해가면서 현재 합이 최대값보다 큰 경우, 갱신합니다.

 

4. 만약 현재 합이 음수인 경우 합을 0으로 바꿉니다.

 

5. 음수만 존재하는 경우는 합이 0일수가 없고, 부분합의 최대값은 음수의 최대값이므로 음수 최대값을 출력

 

N = int(input())
data_list = list(map(int, input().split()))[:N]
max_sum = 0
current_sum = 0
minus_max = -1001
for current in data_list:
    current_sum += current
    if current_sum >= max_sum:
        max_sum = current_sum

    if current_sum < 0:
        current_sum = 0

if max_sum != 0:
    print(max_sum)
else:
    print(max(data_list))