728x90
13398번: 연속합 2
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
분석
- L[N] : 왼쪽에서부터 N을 포함한 최대 연속 합
- L[i]= max(A[i], L[i-1]+A[i])
- R[N] : 오른쪽에서부터 N을 포함한 최대 연속 합
- R[i]= max(A[i], R[i+1]+A[i])
- L[N-1] + R[N+1] : N을 1개 제거한 최댓값 (1개의 수를 삭제할 수 있기 때문)
[1912번] 연속합
1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 n
karla.tistory.com
풀이
n = int(input())
list = list(map(int, input().split()))
# 왼쪽부터 최대 연속합
L=[0]*n
L[0]=list[0]
result=L[0]
for i in range(1, n):
L[i] = max(list[i], L[i-1]+list[i])
result=max(result, L[i]) # 1개도 삭제하지 않았을 때 최댓값
# print(L)
# 오른쪽부터 최대 연속합
R=[0]*n
R[n-1]=list[n-1]
for i in range(n-2, -1, -1):
R[i] = max(list[i], R[i+1]+list[i])
# print(R)
# print(result)
# 수열에서 i삭제 시 최대 연속합
for i in range(1, n-1):
tmp = L[i-1]+R[i+1]
result=max(result, tmp)
print(result)728x90