문제) N 개의 실수 A(1) ~ A(N)이 있을 때, 연속된 수 A(i) ... A(j)의 합이 최대가 되는 값을 구하라.


솔직히 Brute Force 방식으로 풀어도 O(N^3)의 복잡도를 가지므로,

NP-Complete 한 문제는 아니다.

하지만 D.P 연습으로 공부를 하는 거니깐.



D.P 문제 중에는 난이도가 낮은 문제가 아닐까?

반응형

설정

트랙백

댓글

  • MaxSum 2012.08.29 10:42 답글 | 수정/삭제 | ADDR

    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

    • BlogIcon 아자 2012.08.30 10:07 신고 수정/삭제

      Wow, Thanks.
      I didn't know that algorithm.
      I'll modify my article.