글
Dynamic Programming - Maximal Contiguous Subsequent Sum Problem
프로그래밍
2012. 7. 31. 16:44
문제) N 개의 실수 A(1) ~ A(N)이 있을 때, 연속된 수 A(i) ... A(j)의 합이 최대가 되는 값을 구하라.
솔직히 Brute Force 방식으로 풀어도 O(N^3)의 복잡도를 가지므로,
NP-Complete 한 문제는 아니다.
하지만 D.P 연습으로 공부를 하는 거니깐.
D.P 문제 중에는 난이도가 낮은 문제가 아닐까?
반응형
'프로그래밍' 카테고리의 다른 글
Dynamic Programming - Building Bridges, Balanced Partition. (2) | 2012.08.06 |
---|---|
Dynamic Programming - Longest Increasing Subsequence, Box Stacking (0) | 2012.08.03 |
Dynamic Programming - Make Change Problem (2) | 2012.08.01 |
Dynamic Programming - Maximal Contiguous Subsequent Sum Problem (2) | 2012.07.31 |
Dynamic Programming - Knapsack Problem (0) | 2012.07.31 |
Eclipse CDT + Cygwin 으로 C/C++ 개발 환경 설정 관련... (0) | 2012.06.29 |
설정
트랙백
댓글
-
You can calculate the sum in O(n) using Kadane's Algorithm.
int a[n]; // randomized numbers
int t = 0;
int s = INT_MIN;
int k = 0; l = 0;
int j = 0;
for(int i = 0; i < n; i++){
t = t + a[i];
if( t > s ){
s = t;
k = j; l = i;
}
if( t < 0 ){
t = 0;
j = i + 1;
}
}
then s is max sum from k to l on 1D array