최대 연속 부분수열의 합

연속된 원소를 더한 부분 수열의 최댓값을 구하는 문제

 

 

1.  수의 합을 반복적으로 구한다.
2.  이 때 합이 음수이면 그 다음 수부터 다시 시작한다.
3.  합의 최댓값을 도출한다.

 

 

-3 3 5 -3 -7 9 -2 10 -5 -2

 

-3 경우 음수이므로 반영안한다.

현재 합 : 0
합의 최댓값 : 0

 

3 경우

현재 합 : 3
합의 최댓값 : 3

 

 

5 경우

현재 합 : 8
합의 최댓값 : 8

 

 

-3 경우

현재 합 : 5
합의 최댓값 : 8

 

-7 경우

현재 합 : -2 -> 0   음수이므로 0으로 갱신
합의 최댓값 : 8

 

9 경우

현재 합 : 9
합의 최댓값 : 9

 

-2 경우

현재 합 : 7
합의 최댓값 : 9

 

10 경우

현재 합 : 17
합의 최댓값 : 17

 

-5 경우

현재 합 : 12
합의 최댓값 : 17

 

-2 경우

현재 합 : 10
합의 최댓값 : 17

 

 

 

 

dynamic_Sum(n){
dp[0] = n[0]

for i<-1 to n-1
	dp[i] = max(0,dp[i-1]) + n[i];