연속합 실버2 (백준, DP)

import sys


input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))

cnt = 0
for i in arr:
  if i < 0:
    cnt+=1

if cnt == n:
  print(max(arr))
else:
  for i in range(n-1):
    if arr[i] + arr[i+1] > 0:
      arr[i+1] = arr[i]+arr[i+1]
    else:
      arr[i+1] = max(arr[i]+arr[i+1], arr[i+1], 0
 
 print(max(arr))

 

내가 풀이한 코드로 앞과 뒤를 더했을때 값이 -가 아니라면 해당 값을 넣고 -라면 0과 본인, 더한 값 중 가장 큰 값으로 초기화하여 나온 값 중 가장 큰 값을 출력해줬다. 모든 값이 -일 경우는 그냥 모든 배열 중 가장 큰 값을 출력했다. 하지만 이렇게 되면 불필요한 연산이 많은데 이를 해결한 코드는 다음과 같다.

 

n = int(input())
a = list(map(int, input().split()))

for i in range(1, n):
    a[i] = max(a[i], a[i - 1] + a[i])
    
print(max(a))

 

내가 적은 코드를 간략화하면 이렇게 될 듯하다. 본인과 본인과 본인 전을 더했을때 큰 값으로 초기화하는 것만으로도 답이 나온다.