[Algorithm] 프로그래머스 - 연속 펄스 부분 수열의 합

문제

[프로그래머스] 연속 펄스 부분 수열의 합

프로그래머스

 

 

사용 알고리즘

- Kadane's algorithm
> 연속 부분수열(부분배열)의 최대 합을 O(n)에 구하는 전형적인 DP/그리디 기법

해결방법

• 주어진 수열을 돌면서 연속 합이 0보다 작아지면, 더하지 않고 새로 합계를 시작한다
• pulse를 적용하기 위해 1, -1을 가지는 배열을 전체적으로 감싸 수열의 값마다 펄스를 곱해서 처리

 

*Kadane algorithm

i번째 원소까지 봤을 때

• maxEndingHere = i에서 끝나는 최대합
• maxSoFar = 지금까지 본 전체 최대합
• 을 유지하며 한 칸씩 전진

 

점화식:

maxEndingHere = max(a[i], maxEndingHere + a[i])
maxSoFar      = max(maxSoFar, maxEndingHere)

의미: “이전 합에 a[i]를 이어붙일지”, “여기서 새로 시작할지” 선택

 

합계만 반환

static long kadane(int[] a) {
    long maxEndingHere = a[0];
    long maxSoFar = a[0];
    for (int i = 1; i < a.length; i++) {
        long x = a[i];
        maxEndingHere = Math.max(x, maxEndingHere + x);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
}

• 주의: 전부 음수일 때도 동작하도록 초기값을 0이 아니라 첫 원소로 둔다

 

 

구간까지 복원(시작/끝 인덱스)

static class Res { long sum; int L, R; Res(long s,int l,int r){sum=s;L=l;R=r;} }

static Res kadaneRange(int[] a) {
    long best = a[0], cur = a[0];
    int bestL = 0, bestR = 0, start = 0;
    for (int i = 1; i < a.length; i++) {
        if (cur + a[i] < a[i]) { // 새로 시작
            cur = a[i];
            start = i;
        } else {                  // 이어붙이기
            cur += a[i];
        }
        if (cur > best) { best = cur; bestL = start; bestR = i; }
    }
    return new Res(best, bestL, bestR);
}

 

 

 

소스코드

사용언어 : JAVA

class Solution {
    public long solution(int[] sequence) {        
        long maxSum = Long.MIN_VALUE;
        int[] pulse = {-1, 1};

        for (int p : pulse) {
            long now = 0; 

            for (int i=0; i<sequence.length; i++) {
                int pulseNum = sequence[i] * p;
                p *= -1;

                if (now <= 0)
                    now = pulseNum;
                else
                    now += pulseNum;

                if (now > maxSum)
                    maxSum = now;
            }
        }
        
        return maxSum;
    }
    
    // pulse를 상태로
    public long solutionDP(int[] a) {
        long ans = Long.MIN_VALUE;
        long endPlus = Long.MIN_VALUE / 2; //i에서 끝나며, 마지막 부호가 +인 합의 최대값
        long endMinus = Long.MIN_VALUE / 2; //i에서 끝나며, 마지막 부호가 -인 합의 최대값

        for (int x : a) {
            long newEndPlus  = Math.max((long) x, endMinus + x);
            long newEndMinus = Math.max(-(long) x, endPlus - x);
            endPlus  = newEndPlus;
            endMinus = newEndMinus;
            ans = Math.max(ans, Math.max(endPlus, endMinus));
        }
        return ans;
    }
}

pulse를 상태로 (i번째 값 x)

endPlus  = max( +x, endMinus + x )   // 새로 시작(+x) vs 직전이 -로 끝난 것에 +x 이어 붙이기
endMinus = max( -x, endPlus_old - x) // 새로 시작(-x) vs 직전이 +로 끝난 것에 -x 이어 붙이기
ans = max(ans, endPlus, endMinus)

 

 

 

한줄평

카데인 알고리즘 첨들어봤다. . . 연속 부분 수열의 합을 구하래서 처음엔 dp인줄 알았는데 --;;

합계가 음수가 되면 끊고 다시 시작 한다는 법칙만 알고있다면 쉽게 해결할 수 있는 문제인 것 같다