[Algorithm] programmers-161988-연속 펄스 부분수열의 합

import java.util.*;
/*
수열의 각 요소는 -1,1 둘중 하나가 곱해진다.
1. 수열에 1,-1,1 ... 순으로 곱해진 경우
2. 수열에 -1,1,-1 ... 순으로 곱해진 경우 
3. 1,2 두가지 경우를 모두 고려해 최대 수열 찾기

수의 합 구하는 방법
1. 수를 누적시킨다. 음수이면 그 다음 수부터 다시 시작
*/
class Solution {
    static long max = Long.MIN_VALUE;
    public long solution(int[] sequence) {
        makeSequence(sequence, 0);
        makeSequence(sequence, 1);
        return max;
    }

    static void makeSequence(int[] sequence, int pulse){
        int[] seq = Arrays.copyOf(sequence,sequence.length);
        //수열 만들기
        for(int i=0;i<seq.length;i++){
            if(i%2 == pulse){
                seq[i] = seq[i]*-1;
            }
        }

        int idx = 0;
        long sum = 0; // 100,000 * 500,000 이면 500,000,000,000 이므로 정수범위 초과
        while(idx<seq.length){
            sum += seq[idx];
            if(max < sum) max = sum;
            if(sum < 0) sum = 0;
            idx++;
        }
    }
}

• 수열의 각 요소는 둘 중 하나다. -1이 곱해지거나 1이 곱해지거나. 따라서 두 가지 케이스의 수열을 미리 만들어두고 최대연속수열을 구하는 것이다.

• 이 때에 문제조건을 보면 배열의 길이는 500,000개까지 이고 각요소는 -100,000 <= k <= 100,000 이므로 최대 합은 500,000,000,000 가 될 수도 있어서 정수형의 범위를 벗어난다. 따라서 long타입으로 선언해주자.

• 최대부분수열이 아니라 최대연속수열이기 때문에 DP를 통해 풀 필요가 없다. 수를 하나씩 누적하면서 sum값을 통해 max값을 갱신하는데 이 때 수의 합이 음수가 되면 sum을 0으로 초기화 시키고 다음 수부터 다시 누적시킨다.