Lv 3. 연속 펄스 부분 수열의 합

Geisha 2024. 11. 7. 13:30

https://school.programmers.co.kr/learn/courses/30/lessons/161988?language=java

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

https://velog.io/@sheltonwon/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%97%B0%EC%86%8D-%ED%8E%84%EC%8A%A4-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4%EC%9D%98-%ED%95%A9-JAVA

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

문제링크1로 시작하는 누적합 배열과, -1로 시작하는 누적합 배열을 구분하여 풀이를 시작하였다.해당 인덱스 전까지 경우의 수들을 비교하며 최댓값을 탐색하였는데, 줄어드는 이중반복문이라

velog.io

어떻게 풀어야 할지 감이 잡히지 않는 문제였기에

위의 풀이를 보고 풀이 하였다.

class Solution {
    public long solution(int[] sequence) {
        // 2가지 배열로 나눌것 -1, 1 로 시작하는배열로
        int a = 1, b = -1, size = sequence.length;
        long aSum = sequence[0], bSum = sequence[0] * -1, aMin = 0 , bMin = 0, max = Long.MIN_VALUE;
        
        for(int i = 1 ; i <= size ; i++){
            a *= -1;
            b *= -1;
            
            max = Math.max(max, aSum-aMin);
            max = Math.max(max, bSum-bMin);
            
            aMin = Math.min(aMin,aSum);
            bMin = Math.min(bMin,bSum);
            
            if( i == size ) break;
            
            aSum += sequence[i] * a;
            bSum += sequence[i] * b;
        }
        return max;
    }
}