연속 펄스 부분 수열의 합

by

문제 설명

우리는 동일한 길이의 펄스 열로 기차의 연속적인 하위 열의 각 요소를 곱하여 연속적인 하위 펄스 열을 생성하려고 합니다.

펄스 열은 1 또는 -1로 시작하여 다음과 같이 1과 -1 사이를 번갈아가는 열입니다.

예: (1, -1, 1, -1 …) 또는 (-1, 1, -1, 1 …).
예를 들어 시퀀스 (2, 3, -6, 1, 3, -1, 2, 4)의 시퀀스 (3, -6, 1)이 시퀀스 (2, 3, -6)의 연속적인 서브 시퀀스라면 , 1, 4)에 펄스 열 (1, -1, 1)을 곱하면 열은 연속이고 부분 펄스 열은 (3, 6, 1)입니다.

또 다른 예로, 연속적인 하위 시퀀스(3, -1, 2, 4)와 펄스 시퀀스(-1, 1, -1, 1)를 곱하면 연속적인 펄스 하위 시퀀스(-3, -1, -2, 4)가 생성됩니다.

.
정수 시퀀스 sequence가 매개변수로 지정된 경우 solve 함수를 완료하여 연속 펄스 하위 시퀀스의 최대 합을 반환합니다.

제한

  • 1 ≤ 시퀀스 길이 ≤ 500,000
  • -100,000 ≤ 시퀀스의 요소 ≤ 100,000
    • 시퀀스의 요소는 정수입니다.

class Solution {
    public long getMax(long() arr, int index) {
        long res = arr(index);
        for (int i = index; i > 0; i--) {
            if (arr(index) - arr(i) > res) {
                res = arr(index) - arr(i);
            }
        }
        return res;
    }

    public long solution(int() sequence) {
        long() plusSum = new long(sequence.length + 1);
        long() minusSum = new long(sequence.length + 1);

        for (int i = 0; i < sequence.length; i++) {
            if (i % 2 == 0) {
                plusSum(i + 1) = plusSum(i) + sequence(i) * -1;
                minusSum(i + 1) = minusSum(i) + sequence(i);
            } else {
                plusSum(i + 1) = plusSum(i) + sequence(i);
                minusSum(i + 1) = minusSum(i) + sequence(i) * -1;
            }
        }

        int plusIndex = 1, minusIndex = 1;
        long plusMax = Long.MIN_VALUE, minusMax = Long.MIN_VALUE;
        for (int i = 1; i < sequence.length + 1; i++) {
            if (plusMax < plusSum(i)) {
                plusMax = Math.max(plusSum(i), plusMax);
                plusIndex = i;
            }
            if (minusMax < minusSum(i)) {
                minusMax = Math.max(minusSum(i), minusMax);
                minusIndex = i;
            }
        }

        long plusRes = getMax(plusSum, plusIndex);
        long minusRes = getMax(minusSum, minusIndex);

        return Math.max(plusRes, minusRes);
    }
}

** 분할로 해결했습니다 보다 효율적인 해결 방법이 있을 수 있습니다.

'추천 관련글,

** 아쉽게도 제출할 때 불필요한 코드를 제거하지 않았습니다.