BOJ ) 1912번 연속합

https://www.acmicpc.net/problem/1912

1912번: 연속합

1912번 연속합 문제 역시 DP를 사용하는 문제입니다.

 

문제에서 주어진 예제를 사용하여 arr배열이 넣었습니다.

 

여기서 DP[i]는 arr[i]까지의 연속합의 최대값이라고 할 수 있습니다.

 

초기값은 역시 자기 자신으로 시작합니다.

 

두번째 부터 선택을 할 수 있습니다. 10-4 = 6 을 선택할것인지 또는 자기 자신인 -4를 선택할 것인지.

 

DP[i]는 연속합의 최대값이기 때문에 6을 선택하겠습니다.

 

3번째 역시도 6+3 = 9와 자기 자신 3을 선택해야하는데 최대값인 9를 선택해줍니다.

 

그렇게 쭉 칸을 채워나가다가 12를 만나면

 

 

위와같이 -14+12 = -2 보다 자기 자신인 12를 선택하는 경우도 나옵니다.

 

이렇게 표를 다 채우면 최대값은 21일때 33이 최대값이 됩니다. 

 

저희는 직전값 + 자기 자신의값과 자기 자신의값 중 최대값을 비교 했기 때문에 

DP[i]=max(DP[i-1]+arr[i],arr[i])라는 공식이 만들어지게 됩니다.

 

아래는 코드입니다.