[알고리즘] 누적합 구하기

배열의 누적합 구하기 O(n)

• 1차원 배열 A에서 A[3:10] 의 합을 구하라
• 푸는 방법은?
  • A[0:x] 까지의 합을 저장하고 있는 pSum[x] 배열을 만든다
  • A[3:10] 까지의 합은 = pSum[10] - pSum[2]로 구할 수 있다
  • 당연히 시간 복잡도는 O(n)이 된다
• 최대 누적합 구하기
  • 다이나믹 프로그래밍을 사용
  • D[i] 자신을 포함하는 부분합을 만든다. 그때 부분합이 가능 큰 것을 저장한다.

//A는 배열
D[1] = A[1];
ans = MIN;

for(i=2; i<=N; i++){
		D[i] = max(D[i-1] + A[i], A[i]);
		ans = max(ans, D[i]);
}

• • 하나를 빼도 되는 누적합 구하기

D2[N] = A[n];
for(i=N-1; i>=1; i--){
		D2[i] = max(D2[i+1] + A[i], A[i]);
}

//k번째를 하나 빼고 구하는 누적합
for(k=2; k<=N-1; k++){
		ans = max(D[k-1] + D2[k+1], ans)
}

🦔 백준 풀어볼 문제들

11659 구간 합 구하기 4 기본 문제
10211 Maximum subarray Problem 기본 : (길이가 정해지지 않은) 최대 누적합 구하기 문제
2003 수들의 합 2 : 이거는 투 포인터로 푸는 문제다
13998 연속합2 최대 누적합 응용
10986 나머지합 응용

 

그러나 세그먼트 트리를 사용하면 배열의 누적합을 무려 O(logn)만에 풀 수 있게 된다. 다음시간에 계속!