연속합
-
[백준] 1912번 연속합알고리즘/백준 2021. 8. 22. 23:48
문제 링크 풀이 점화식 d[i]는 i번째 요소까지의 연속합의 최대 값입니다. 문제에서 수는 한 개 이상 선택해야 한다고 했으므로 d[i-1]번째 수와 arr[i]를 더했을 때의 값이 arr[i]의 값보다 작다면 i번째 요소인 arr[i] 자체가 연속합의 최대 값이 됩니다. 그러므로 다음과 같은 점화식을 세울 수 있습니다. answer의 초기 값이 -100000000인 이유는 요소에 음수 값이 있을 수 있기 때문입니다. d[i] = max(d[i-1] + arr[i], arr[i]) 코드 #include int max(int a, int b) { return a > b ? a : b; } int main() { int N; scanf("%d", &N); int d[100001] = {}; int arr[1..