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

1. 문제

프로그래머스

 

[문제 요약]

• 부분 수열의 합 중 가장 큰 값을 구하라

 

2. 생각

1. 코딩테스트는 두 가지 유형이 있지
문제가 길어 문제가 요구하는 방향을 이해하면 풀 수 있는 문제와
문제가 짧어 뭘 구하라는지 알겠는데 어떻게 구해? 하는 문제
이 문제는 후자의 경우... 문제 보자마자 든 생각: 뭐 어떻게 구해?

2. 펄스 수열 이용해서 2개의 배열 만드는 것까지는 쉬움

3. "수열의 부분 수열의 최댓값" 이거 구하는게 관건같은데...

하나씩 다 만들어보기에는 sequence의 길이 제한이 커서 안될꺼같다

4. 30분정도 고민해보고 인터넷 찾아봤는데 이미 "카데인 알고리즘"이라고 만들어져(?)있음

5. 오늘도 하나 배웠다.

 

3. 코드

class Solution {
    public long solution(int[] sequence) {
        int n = sequence.length;
        
        int[] pulse1 = new int[n];
        int[] pulse2 = new int[n];
        
        for(int i = 0; i < n; i++) {
            pulse1[i] = sequence[i] * (i % 2 == 0 ? 1 : -1);
            pulse2[i] = sequence[i] * (i % 2 == 0 ? -1 : 1);
        }
        
        long max1 = kadane(pulse1);
        long max2 = kadane(pulse2);
        
        return Math.max(max1, max2);
    }
    
    private long kadane(int[] sequence) {
        long maxSum = sequence[0];
        long currentSum = sequence[0];
        
        for(int i = 1; i < sequence.length; i++) {
            // 현재까지의 합 계속 갱신(시작 갱신)
            currentSum = Math.max(sequence[i], currentSum + sequence[i]);
            
            // 전체 최대값 갱신
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return maxSum;
    }
}