[Programmers] 카데인 알고리즘

연속 펄스 부분 수열의 합
https://school.programmers.co.kr/learn/courses/30/lessons/161988

이 문제의 핵심 아이디어는 두가지이다.

1. 연속 부분 수열을 골라도 -1, 1, -1... 패턴과 1, -1, 1... 패턴 두가지만 나온다는 점
2. 연속 부분 수열의 최대 합을 구하는 최적화 알고리즘

그렇기에 두가지 패턴을 적용한 배열 두개를 카데인 알고리즘을 통해서 Max 값을 구해주는 것이 핵심

카데인 알고리즘?

최대 부분 배열 합을 O(n) 시간에 해결하는 알고리즘

간단하게 3, 1, -5, 4, 2 라는 배열이 있으면

3 -> 3+1= 4 -> 4-5= -1 -> -1 + 4 = 3 (초기화!) = 4 -> 4+2=6

중간에 그 전의 합이 -1이기 때문에 값이 줄어드는 곳을 다시 자기 자신으로 초기화 한다.
그렇게 한번의 순회로 6이 최대값임을 알게된다.

코드

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

class Solution {
    static int n;
    static long answer;
    static int[] arr1, arr2;
    public long solution(int[] sequence) {
        answer = Long.MIN_VALUE;
        n = sequence.length;
        
        arr1 = new int[n];
        arr2 = new int[n];
        // int 배열 초기화를 하면 0이기 때문에 이런 식으로 작성
        for(int i=0;i<n;i++){
            if(i % 2 == 0) {
                arr1[i] += sequence[i];
                arr2[i] -= sequence[i];
            }
            else{
                arr1[i] -= sequence[i];
                arr2[i] += sequence[i];
            }
        }
        // 두 배열의 연속 펄스 부분 수열의 합의 최댓값중 큰 값이 정답 
        return Math.max(kadein(arr1,n), kadein(arr2,n));
    }
    
    public static long kadein(int[] arr, int len){
        long max = Long.MIN_VALUE;
        long sum = 0;
        
        for(int i=0;i<len;i++){
            long newSum = sum + arr[i];
            // 새로운 합이 나보다 크면 계속
            if(newSum >= arr[i]){
                sum = newSum;
                
                if(newSum > max) max = newSum;
            }
            // 작으면 나로 초기화 
            else{
                sum = arr[i];
                
                if(sum > max) max = sum;
            }
        }
        
        return max;
    }  
    
}