[백준][DP][카데인 알고리즘] 연속합

연속합

 

• 첫 풀이
  • 오류 원인
  • if i == 0:
        dp[i] = max(0, numbers[i])
  • -5 -2 -3 일때 max(dp)에서 dp[0]=0 이 채택되면 없는 값이 선택 되는 것

n = int(input())
numbers = list(map(int, input().split()))
dp = numbers[:]
for i in range(n):
    if i == 0:
        dp[i] = max(0, numbers[i])
        continue
    dp[i] = max(numbers[i], dp[i-1]+numbers[i])

print(max(dp))

 

• 내 풀이
  • 해당 위치값부터 시작하거나
  • 이전값에서 해당위치값을 더하거나
  • 2가지 경우 중 선택

n = int(input())
numbers = list(map(int, input().split()))
dp = numbers[:]
for i in range(1, n):
    dp[i] = max(numbers[i], dp[i-1]+numbers[i])

print(max(dp))