[백준, 1912번] 연속합 (다이나믹 프로그래밍, DP, 수열, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 연속합"문제는 주어진 배열에서 연속된 수들의 합이 최대가 되는 부분 배열의 합을 구하는 문제입니다. 이 때 수열에서 숫자를 선택할 때는 연속된 수를 선택해야하는 것이 핵심입니다.

 

이 문제를 효율적으로 해결하기 위해 다이나믹 프로그래밍 알고리즘을 사용합니다.

[Algorithm] 동적 계획법(Dynamic Programming, DP, Java) 알아보기

 

연속된 값을 선택해야 하므로, 현재까지의 연속합에 현재 값을 더한 값과 현재 값 중 더 큰 값을 선택합니다. 이렇게 하면 각 단계에서 최댓값을 유지할 수 있으며, 최종적으로 연속합 배열에서 가장 큰 값을 반환하면 됩니다.

 

따라서 점화식은 다음과 같습니다.

Max(현재까지 연속합 + 현재 값 , 현재 값)

 

예제 입력 1번을 예로 설명을 하자면,

 

첫 번째 원소의 최대 연속합은 그 값 자체입니다.

 

이후, 현재까지의 연속합과 다음 값을 더한 값(A)과 다음 값부터 새롭게 시작하는 값(B)을 비교하여 더 큰 값을 채워나갑니다.

 

예를 들어, 7번째 인덱스를 채울 때 현재까지의 연속합은 -14이고, 현재 값을 더하면 -2가 됩니다. 그러나 새롭게 시작한다면 12를 선택할 수 있으므로, 이 경우에는 12를 선택하는 것이 더 유리합니다.

 

전체 코드