문제

문제링크

접근

• 1로 시작하는 누적합 배열과, -1로 시작하는 누적합 배열을 구분하여 풀이를 시작하였다.
• 해당 인덱스 전까지 경우의 수들을 비교하며 최댓값을 탐색하였는데, 줄어드는 이중반복문이라 O(nlogn)의 시간복잡도를 가진다. -> 시간초과
• O(n) 수준의 시간복잡도를 고민하다가 누적합을 더하는 과정에서 현재 인덱스까지의 최소합을 저장하여 차를 구하도록 하였다.
• 각 인덱스의 차를 최대값과 비교하여 최대값을 찾는다.

소스 코드

class Solution {
    public long solution(int[] sequence) {
        int a = 1, b = -1, size = sequence.length;
        long aSum = sequence[0], bSum = sequence[0] * -1, aMin = 0, bMin = 0, max = Long.MIN_VALUE;
        
        for (int i = 1; i <= size; i++) {
            a *= -1;
            b *= -1;
            
            max = Math.max(max, aSum - aMin);
            max = Math.max(max, bSum - bMin);
            
            aMin = Math.min(aMin, aSum);
            bMin = Math.min(bMin, bSum);
            
            if (i == size) break;
            
            aSum += sequence[i] * a;
            bSum += sequence[i] * b;
        }
        
        return max;
    }
}