[백준][누적합] 1912. 연속합

1912. 연속합

 

• 내 풀이
  • 이전 까지의 합이 0보다 작으면 현재 수랑 비교해서 큰값으로 tmp 업데이트
    • 이후, ans와 비교해서 업데이트
  • 합이 0보다 크면 현재 값을 더한 값과 기존의 max값과 비교

 

n=int(input())
nums=list(map(int,input().split()))
tmp=-float('inf')
ans=-float('inf')

for num in nums:
    if tmp<0:
        tmp=max(tmp,num)
        ans=max(ans,tmp)
        continue

    tmp+=num
    ans=max(ans,tmp)

print(ans)

 

 

• 다른 풀이
  • 기존 값 리스트 lst
  • 최대값 리스트 dp
  • 이전값과 현재값 더한 결과가 0보다 크면 업데이트
  • 두개 더한 값보다 현재값만 하는게 더 크면 현재값으로 업데이트

n = int(input())
lst = [0]+list(map(int, input().split()))

dp = [lst[i] for i in range(n+1)]
for i in range(1, n+1):
    if dp[i-1]+lst[i] > 0:
        dp[i] = dp[i-1]+lst[i]
    if dp[i-1]+lst[i] < lst[i]:
        dp[i] = lst[i]


print(max(dp[1:]))