119쪽 최대구간합 동적계획법 점화식질문

  • ALGO_HONEY
    ALGO_HONEY

    이제 막 책을 보고있는 뉴비입니다T^T. 119쪽 동적계획법 바로 위에있는 분할정복 알고리즘도 이해하는데 오래걸렸는데 동적계획법 점화식은 이해가 잘안되네여 흑ㅠㅠ

    119쪽 여백을 두고 나와있는 점화식

    • maxAt(i) = max(0, maxAt(i-1)) + A[i]

    이거 잘못나온거 아닌가요? 그냥 간단하게 [2,100,-3] 만 생각해봐도 뒤에 A[i]가 음수니까 더하면안되잖아요. 참고로 책에는 maxAt(i)정의가

    • A[i]를 오른쪽 끝으로 갖는 구간의 최대합을 반환하는 함수

    라고 되어있습니다.

    근데 바로 아래에 나와있는 코드

    int fastestMaxSum(const vector<int>& A) {
    int N = A.size(), ret = MIN, psum = 0;
    for(int i =0; i < N; ++i) {
      psum = max(psum, 0) + A[i];
      ret = max(psum, ret);
    }
    return ret;
}

    이거는 맞는거 같아서..
    진정 저기 점화식을 코드로 풀어쓴게 저 코드가 맞나요?
    점화식에는 psum변수에 대한 정보가 없는거같은데..
    만약 잘못된 점화식이면 어떻게 점화식으로 풀어쓰나요.
    고수님들 알려주세요ㅠㅠ 이것때매 잠을 못자고있넹


    10년 전
8개의 댓글이 있습니다.
  • Being
    Being

    정의가 "A[i]를 오른쪽 끝으로 갖는 최대 구간"이므로 -3이건 -100이건 반드시 더해져야 맞지 않을까요?


    10년 전 link
  • ALGO_HONEY
    ALGO_HONEY

    2 100 -3 에서 최대구간합은 102아닌가요??? 만약에 -3을 더하면 99가되서 최대구간합이아닌거같은데ㅠ


    10년 전 link
  • Kureyo
    Kureyo

    maxAt(i) 는 i를 무조건 우측끝으로 포함하는 경우로 한정지을 경우의 최대값이기 때문에 maxAt(N-1)이 최적해가 아닐 수 있습니다.
    문제에서 원하는 답은, 정답구간의 우측끝이 항상 [0,N-1]구간에 속할것이므로 max{ maxAt(0), maxAt(1), ... maxAt(N-1) } 이 될것입니다.


    10년 전 link
  • Being
    Being

    정의를 잘 생각해 보세요. 우리가 각 원소를 끝으로 하는 최대구간합을 각각 구하고 있지요? 다시 말해, 우리가 뒤로 갈수록 점점 답이 좋아지도록 구성해서 마지막 A[N]만 알고자 하는 것이 아니라 그저 A[i]를 구하기 위해 A[i-1]을 활용하고 있을 뿐입니다.


    10년 전 link
  • Being
    Being

    아이고 A가 아니군요 maxAt입니다 ㅠ


    10년 전 link
  • Kureyo
    Kureyo

    코드에 대해 첨언 하자면 psum은 maxAt에 대응되고 ret는 max{ maxAt(0), maxAt(1), ... }에 대응이 됩니다


    10년 전 link
  • ALGO_HONEY
    ALGO_HONEY

    다들 감사합니다ㅠㅠ!! 이제이해갔어요 점화식 ㅋㅋㅋㅋ 우측끝으로갖는 최대구간합이라는 말을잘못이해했었네요. 전 첨에 maxAt(i)가 최종답을뜻하는걸로 인식하고 그래서 단순히 A[i]가 우측끝에 '위치'해있다는걸로 이해했었는데..
    최종답은 max(maxAt(0),maxAt(1)...maxAt(i))이고 우측끝을 구간내에 꼭 포함시켰을때 최대구간합이라는 의미였었군용.


    10년 전 link
  • Kureyo
    Kureyo

    :)


    10년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.