https://www.acmicpc.net/problem/13398
실패이유 : 시간초과
시간초과코드
n = int(input())
a = [0] + list(map(int, input().split()))
d = [-1001] * (n + 1)
idx = []
d[1] = a[1]
for i in range(2, n + 1):
d[i] = a[i]
if d[i] < d[i - 1] + a[i]:
d[i] = d[i - 1] + a[i]
if a[i] < 0:
idx.append(i)
ans = max(d)
for minus in idx:
a_copy = a[:]
a_copy.pop(minus)
d = [-1001] * (n + 1)
d[1] = a_copy[1]
for i in range(2, n):
d[i] = a_copy[i]
if d[i] < d[i - 1] + a_copy[i]:
d[i] = d[i - 1] + a_copy[i]
ans = max(ans, max(d))
print(ans)
- 먼저 아무것도 빼지 않고 연속합을 구한다.
- 이후, 음수값들을 하나씩 빼면서 다시 연속합을 모두 구한다.
- 해당 방식으로 풀 경우,
O(n^2)시간복잡도로 시간초과 발생
정답코드
n = int(input())
a = [0] + list(map(int, input().split()))
d = [-1001] * (n + 1)
dr = d[:]
d[1] = a[1]
for i in range(2, n + 1): # 앞에서 부터 최대 연속합을 구한다.
d[i] = a[i]
if d[i] < d[i - 1] + a[i]:
d[i] = d[i - 1] + a[i]
dr[n] = a[n]
for i in range(n - 1, 0, -1): # 뒤에서 부터 최대 연속합을 구한다.
dr[i] = a[i]
if dr[i] < dr[i + 1] + a[i]:
dr[i] = dr[i + 1] + a[i]
ans = max(d) # 하나도 빼지 않은 경우의 최대 연속합을 구한다.
for i in range(2, n): # 하나를 뺀 경우의 최대 연속합을 구한다.
if ans < d[i - 1] + dr[i + 1]:
ans = d[i - 1] + dr[i + 1] # i 번째 수를 뺀 연속합을 의미한다.
print(ans)
O(n)시간복잡도로 문제 해결 가능d는 앞에서부터 구한 연속합 리스트dr은 뒤에서부터 구한 연속합 리스트d[i-1] + dr[i+1]은 i 번째 수를 제외한 뒤의 최대 연속합을 의미한다.
출처 : 코드플러스 - 알고리즘 기초 1/2 강의
https://code.plus/course/41
