[JAVA72] 연속 펄스 부분 수열의 합 (LEVEL3)

연속 펄스 부분 수열의 합 (LEVEL3)

문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 

펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.
예를 들어 수열 [2, 3, -6, 1, 3, -1, 2, 4]의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하면 연속 펄스 부분수열은 [3, 6, 1]이 됩니다. 또 다른 예시로 연속 부분 수열 [3, -1, 2, 4]에 펄스 수열 [-1, 1, -1, 1]을 곱하면 연속 펄스 부분수열은 [-3, -1, -2, 4]이 됩니다.
정수 수열 sequence가 매개변수로 주어질 때, 연속 펄스 부분 수열의 합 중 가장 큰 것을 return 하도록 solution 함수를 완성해주세요.

 

---

summary

연속 펄스 부분 수열의 합 중 가장 큰 값 구하기

• 펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열

 

strategy

그리디 

• 각 원소를 확인할 때마다 최선의 값 (가장 큰 값)을 가지고 있음
• 펄스 수열이 1로 시작하는 경우와 -1로 시작하는 경우 두 가지 확인함
• 원소와 펄스값이 음수인 경우
  • 합이 음수인 경우 sum = 0 초기화
• 원소와 펄스값이 양수인 경우
  • 합이 음수인 경우 sum = current 로 초기화
  • 합이 양수인 경우 sum 유지 (최대값인지 체크)

 

note

• 1 ≤ sequence의 길이 ≤ 500,000
• 100,000 ≤ sequence의 원소 ≤ 100,000

 

import java.util.*;
import java.io.*;

class Solution {
    static long answer;
    public long solution(int[] sequence) {

        cal(1, sequence); // 펄수 수열 첫 원소가 1인 경우
        cal(-1,sequence); // 펄수 수열 첫 원소가 -1인 경우
        
        return answer;
    }
    
    static public void cal(int pul, int[] sequence) {
        long sum = 0;
        for(int idx = 0; idx < sequence.length; idx++) {
            int current = sequence[idx] * pul;
            sum += current;
            if(current > 0) { // 현재원소가 양수
                if(sum > 0) answer = Math.max(sum, answer);
                else sum = current; // 현재 원소부터 재시작
            } else { // 현재원소가 음수
                if(sum < 0) sum = 0; // 재시작
            }
            
            pul *= -1; // 펄스 수열
        }
    }
}

 

MEMO

• for문 한번 돌면서 두가지 펄스를 한번에 체크해도 되지만, 가독성과 재사용성을 신경써서 나눠봤다.