연속합 (DP or 투 포인터)

 

📍 연속합 정의

주어진 수열에서 연속된 부분 수열의 합 중 최댓값을 구하는 문제

 

 

📍 해결 방법

 ①  DP  

◾ WHEN?   입력 크기가 작은 경우

◾ HOW?      이전 부분 수열의 합에 현재 수를 더하면서 최댓값 업데이트

                     (점화식 :  현재 수를 더할 것인지 or 현재 수부터 새로운 부분 수열을 시작할 것인지 결정)

 

 

 

 ②  투 포인터  

◾ WHEN?   입력 크기가 큰 경우 &  수열 순서가 중요한 문제      (수열의 순서를 유지하며 부분 수열을 구할 수 있으므로)

◾ HOW?      시작 포인터와 끝 포인터를 조정하면서 합을 계산하고, 최댓값 업데이트

 

 

 

 

➕ 예제

[백준/JAVA] 1644번: 소수의 연속합