[백준] 1912 연속합, python, C

https://www.acmicpc.net/problem/1912

1912번: 연속합

N = int(input())
nums = list(map(int, input().split()))
dp = [-200000000 for _ in range(N + 1)]
for i in range(N):
    dp[i + 1] = max(dp[i] + nums[i], nums[i])
print(max(dp))

처음엔 슬라이딩 윈도우라고 생각해서 브루트포스 방식으로 접근했는데 시간초과가 나왔다. O(N^2)

그래서 memoization을 사용하여 dynamic programming으로 접근하였다.

dp의 초기값은 최저값인 -1000*100000인데 혹시 몰라 2를 곱해서 사용하였다.

순회하면서 최대값을 찾게 되는데 현재 위치의 값과 이전까지의 최대값을 더한 것과 현재 위치의 값을 비교해서 더하게 되면 각 자리에 만들수 있는 최대값이 저장된다.

한번 순회한 이후 dp의 최댓값을 다시 찾아 출력하면 된다.

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAX(x, y) x>y? x : y

int main() {
    int N, i, ans;
    int nums[100000] = { 0, };
    int dp[100001];
    scanf("%d", &N);
    for (i = 0; i < N; i++)
        scanf("%d", &nums[i]);


    for (i = 0; i < N + 1; i++)
        dp[i] = -200000000;

    ans = dp[0];
    for (i = 0; i < N; i++)
    {
        dp[i + 1] = MAX(dp[i] + nums[i], nums[i]);
        if (ans < dp[i + 1])
            ans = dp[i + 1];
    }
        
    printf("%d\n", ans);
	return 0;
}

파이썬이랑 크게 다를바 없는 알고리즘이다.

다른건 배열의 크기를 고정시켜놓은 것과 dp 초기화 부분이다.

 

---

이것도 실버 문제라 오래걸리지 않았다.