백준 문제풀이
10211번 : Maximum Subarray / silver 4 / 누적합
RonLee
2023. 2. 10. 10:22
https://www.acmicpc.net/problem/10211
10211번: Maximum Subarray
크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있
www.acmicpc.net
'''
10211번 : Maximum Subarray / silver 4 / 누적합
'''
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
n = int(input())
arr = list(map(int, input().split()))
# 누적합 구하기
pre_sum = [0 for _ in range(n)]
pre_sum[0] = arr[0]
for i in range(1, n):
pre_sum[i] = pre_sum[i - 1] + arr[i]
# 누적합 활용 최대 부분배열 도출
max_res = arr[0]
for x in range(n):
for y in range(x, n):
if x == 0:
res = pre_sum[y]
else:
res = pre_sum[y] - pre_sum[x - 1]
if max_res < res:
max_res = res
print(max_res)
누적합 활용
- 여러 인덱스 값들을 규칙성 있게 많이 계산해야 할 경우, 누적 합을 많이 활용 한다.
누적합을 활용하지 않는다면,
길이가 1,2,3,4,... 일때 경우들을 모두 찾아
하나하나 인덱스들을 모두 더하고 -> 비교 하는
전체 탐색 (부르트포스)를 실행하게 될 것 같다.