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

1. Prefix Sum

• 0~i까지 구간의 합

 

코드

for (int i = 0; i < n; i++) {
    ps[i] = i-1>=0 ? ps[i-1] : 0 + arr[i];
}

 

2. Suffix Sum

• i~n까지 구간의 합

코드

for (int i = n-1; i >= 0; i--)
	ps[i] = i+1<n ? ps[i+1] : 0 + arr[i];
}

 

 

3. Target Subtotal

Kadane's Algorithm

• i번째 원소를 끝으로 하는 최대 연속 부분합
• ✅ 최대 부분 배열 합을 효율적으로 찾기 위한 알고리즘
• ➡️ O(n): 연속된 부분배열의 최대값을 선형으로 찾을 수 있음

 

코드

for (int i = 0; i < n; i++) {
    dp[i] = Math.max(i-1>=0 ? dp[i-1] : 0 +arr[i], arr[i]);
}

 

✅ dp[i-1] + 현재 방문한 원소 or 현재 방문한 원소 대소 비교를 통해 dp[i]를 갱신해감

 

 

출처

• Wiki - Prefix Sum
• Wiki - Maximum subarray problem