[백준]1912 연속합 #dp

1.풀이

(1) 연속된 수의 합이므로 수열이 모두 양수라면 당연히 모든수를 다합하는것이 최대연속합이 된다.

하지만 음수가 있다면 달라진다.

​

(2) 점화식 (dp[i] : i번째 숫자를 포함하는 최대연속합)

 - 소스코드1

  dp[i]=max(L[i],dp[i-1]+L[i]) 

 - 소스코드2

  그전까지 값(nowSum)이 음수이면 -> 이전값과 더하지 않고 새로시작

  그전까지 값(nowSum)이 양수이면 -> 이전값과 더함

​

2.소스코드

(1) 소스코드1

n=int(input())
L=list(map(int,input().split()))
dp=[0 for i in range(n)]
nowSum=0
for i in range(n):
    nowSum=max(nowSum+L[i],L[i])
    dp[i]=nowSum
print(max(dp))

 

(2) 소스코드2

n=int(input())
L=list(map(int,input().split()))
dp=[0 for i in range(n)]
nowSum=0
for i in range(n):
    if nowSum>=0:
        nowSum=nowSum+L[i]
    else:
        nowSum=L[i]
    dp[i]=nowSum
print(max(dp))