1912번 연속합(DP) - ☆

#문제링크 : https://www.acmicpc.net/problem/1912

<전략>

1. 처음에는 수열에서 i번째에 음수가 나오면 그 음수가 그전까지의 d[i-1]와 더했을때, 음수가 되면 0으로 넣고, 양수가 되면 그 양수값을 그대로 가져가는 방법으로 했지만, 모든 수가 음수일 경우 이 방법은 틀리게 된다. 

2. 두가지 조건을 생각해야한다. ⓐi번째 값이 연속합에 포함될건지 ⓑ새로운 연속합을 시작할건지

3. 음수를 포함했을때, 최대가 나오는 경우가 있기 때문에, d[i]는 i번째값까지의 연속합 중 최대값을 가지는 것이 아니라, i번째의 값이 포함되었을때와 포함되지 않고 새로 시작할때의 값중 큰 값으로 d[i]를 정의해야 한다.

※주의사항

1. 문제에서 물어보는 원리를 곰곰히 생각하자.

2. d[i]가 꼭 i번째의 최대 연속합이 아닐 수 있음을 명심하자.

 

Code