✅ DP

문제

링크

1. 문제 접근 및 해결 로직

경우의 수는 세가지로 나누어 진다.

1. n-1과 n이 연속됨
2. n-1과 n이 연속되지 않음, n의 자리수를 덧셈에 사용하지 않은 경우
3. n-1과 n이 연속되지 않음, n의 자리수를 덧셈에 사용한 경우

$f(n)$ 을 n개의 수열에서 연속된 수의 합 중 가장 큰 값이라고 하면
위의 경우에 따라

1. $f(n)=f(n-1)+arr[n]$
2. $f(n)=f(n-1)$
3. $f(n)=arr[n]$ : n-1과 n이 연속되지 않기 때문에 arr[n] 자체가 연속된 가장 큰 값이 된다.

세가지 경우 중 가장 큰값이 $f(n)$이 된다.

• 정의
  $f(n)$ : n개의 수열에서 연속된 수의 합 중 가장 큰 값
• 구하는 답
  $max(f(1),f(2),f(3),...,f(n))$
• 초기값
  $f(1)=arr[1]$
• 점화식
  $f(n)=max(f(n-1)+arr[n],f(n-1),arr[n])$

• 구하는 답
  연속된 수의 합이 가장 큰 경우가 $n-1$이전 수열에 있을 수도 있는 조합일 수도 있으므로 전체에서 가장 큰 수를 구해준다.

2. 코드

3. 시간 복잡도 분석

경우의 수를 모두 구하므로
$O(N)$

4. 문제에서 중요한 부분

DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항