[Java 코딩테스트] 프로그래머스 연속 펄스 부분 수열의 합 풀이 / 연속 배열의 최대 합

Problem

• 연속 펄스 부분 수열의 합

darklight

sublimevimemacs

Java

문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [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 함수를 완성해주세요.

---

제한 사항

• 1 ≤ sequence의 길이 ≤ 500,000
• 100,000 ≤ sequence의 원소 ≤ 100,000
  • sequence의 원소는 정수입니다.

---

입출력 예

sequence	result
[2, 3, -6, 1, 3, -1, 2, 4]	10

---

입출력 예 설명

주어진 수열의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하여 연속 펄스 부분 수열 [3, 6, 1]을 얻을 수 있고 그 합은 10으로서 가장 큽니다.

Description

• 솔직히 이게 3레벨이라 믿기지 않는 문제. 1레벨이면 충분할 것 같다.
• 설명에서 주어진 바와 같이 배열의 각 인덱스에 1과 -1을 번갈아가며 곱해준 것과 -1과 1을 번갈아가며 곱해준 것 중 연속 합이 큰 것을 고르면 된다.
• DP를 이용해 쉽게 풀 수 있는데, 현재 값을 더 했을 때의 최대 값과 더하지 않았을 때의 최대 값을 비교하면 된다.
• 최대 값을 저장하기 위한 1차원 DP 배열을 선언한다.
  • long[] sum = new long[length]
• 주어진 예제를 이용해 설명해 보면
  • 먼저 1, -1, 1, -1, … 을 곱한 배열은 다음과 같다.
  • [2, -3, -6, -1, 3, 1, 2, -4]
  • 여기에 대해 0번 인덱스 부터 하나씩 옮겨가며 다음과 같이 비교한다.
    • if 문의 비교연산은 다음 의미를 갖는다.
      • 이전까지의 합과 현재 합을 더했을 때, 0보다 큰가? 즉, 음수가 되지 않았는가에 대한 비교이다.
      • 만약 0 이하라면, sum[i] → 0으로 설정하여 현재 인덱스 까지의 연산을 초기화한다.
  • if(sum[i-1] + sequence[i] > 0) sum[i] = sum[i-1] + sequence[i]; else sum[i] = 0;
  • 그런 다음, answer와 현재까지의 합에 대하여 크기 비교를 수행한다.
    • if 문의 비교 연산은 다음 의미를 갖는다.
      • 이전 index까지 배열의 합이 answer보다 크다는 것은, 이전의 최대 합 보다 현재의 최대 합이 더 크다는 뜻이다. 따라서 answer을 갱신한다.
      • 그렇지 않을 경우, 이전에 찾은 answer가 최대 값이기 때문에 answer를 유지한다.
  • if(sum[i] > answer) answer = sum[i];

Result

import java.util.*;
class Solution {
    public long solution(int[] sequence) {
        long answer = 0;
        int length = sequence.length;
        long[] sum = new long[length];
        int m = 0, n = 1;

        if(length == 1){
            return Math.max(sequence[0], sequence[0] * -1);
        }

        //* [1, -1, 1, -1] ... 을 곱했을 때
        for(int i = 0; i < length; i++){
            if(i % 2 == 1){
                sequence[i] *= -1;
            }

            //* Business Logic
            if(i == 0){
                sum[i] = Math.max(sequence[i], 0);
                continue;
            }
            sum[i] = Math.max(0, sum[i-1] + sequence[i]);
            answer = Math.max(answer, sum[i]);
        }

        //* [-1, 1, -1, 1] ... 을 곱했을 때
        for(int i = 0; i < length; i++){
            sequence[i] *= -1;

            //* Business Logic
            if(i == 0){
                sum[i] = Math.max(sequence[i], 0);
                continue;
            }
            sum[i] = Math.max(0, sum[i-1] + sequence[i]);
            answer = Math.max(answer, sum[i]);
        }

        return answer;
    }
}