1912번

1912번 - 연속합

문제의 크기가 커서 완전 탐색 보다는 바로 DP로 풀어야 겠다고 생각했다.

점화식

D[N]은 N을 마지막 수로 하는 부분수열의 최대 연속 합.

점화식을 풀면서

D[N]=max(A[N],maxsum(n-1)+A[N]); 을

D[N]=max(D[N],maxsum(n-1)+A[N]); 과 계속 헷갈려서 풀었다.

D[N]을 만드는 방법은 연속된 합일 때, 혹은 N번째 자릿 수 하나인 A[N]일 때 두가지 이므로 다음부터는 잘 따져서 생각해봐야 겠다.

이 문제를 풀면서 내 실수 및 중요한 점을 발견했다.

1. 분명 수열에는 음수가 존재하는데, 너무 문제 풀기만 하다 보니까 또 문제를 제대로 읽지않고 

양수만으로 계산하여 비교할 ans , 배열 D 값들을 0으로 초기화 하다 보니 제대로 된 값이 처음에 나오지 않았다.

=> 문제를 꼭 제대로 읽고 생각하고 풀기를.... 예전에 풀었던 문제를 다시 푸니 스스로 다 안다고 착각해서 그런 것 같다.

2. memset 함수를 사용하였는데, 너무 큰 음수를 넣어서 그런지는 모르겠지만, memset을 통한 초기화가 되지 않았다.

나는 문제를 푸는데만 함수들을 사용하였는데, 어떠한 이유인지는 모르겠다.. memset이 음수 값으로 어느정도까지 초기화가 가능한지..

이 부분은 따로 검색을 해서 알아봐야 할 것 같다. 디버깅 중에 찾아낸 오류.

앞으로는 캐시 값들을 memset 초기 보다는 귀찮더라도 for문으로 초기화 하는 버릇을 들여야 겠다.

<완성 코드>

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int N;
int A[100001];
int D[100001];
int ans = -2100000000;
int maxsum(int n)
{
 
    if (n == 0)
    {
        return A[0];
    }
 
    if (D[n] != -2100000000)
    {
        return D[n];
    }
 
    D[n]=max(A[n],maxsum(n - 1)+A[n]);
 
    return D[n];
}
int main()
{
    cin >> N;
 
    //memset(D, -10000000, sizeof(D));
    
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
 
    for (int i = 0; i < 100001; i++)
    {
        D[i] = -2100000000;
    }
 
    for (int i = 0; i < N; i++)
    {
        ans=max(ans,maxsum(i));
    }
 
    cout << ans << endl;
    return 0;
}