[고급 알고리즘] Dynamic Programming: Prefix Sum

1. Prefix Sum

• 0~i까지 구간의 합

 

2. Suffix Sum

• n~i까지 구간의 합

 

3. Target Subtotal

Kadane's Algorithm

• 최대 부분 배열 합을 효율적으로 찾기 위한 알고리즘

 

동적 프로그래밍

• i번째 까지 원소의 최대 배열 부분 합을 관리
• dp[i-1] + 현재 방문한 원소 or 현재 방문한 원소 대소 비교를 통해 dp[i]를 갱신해감

 

시간복잡도

• O(n)
• 최대값을 선형으로 찾을 수 있음

 

 

출처

• Wiki - Prefix Sum
• Wiki - Maximum subarray problem