[프로그래머스] 연속 펄스 부분 수열의 합 - Java

문제

https://school.programmers.co.kr/learn/courses/30/lessons/161988

프로그래머스

 

---

sequence 배열에 -1, 1, -1 · · · 순서로 곱한 배한 배열, 1, -1, 1 · · · 순서로 곱한 배열 각각의 배열에서 연속된 부분 배열의 합이 가장 큰 값을 찾아 return 해주면 된다.

연속된 부분 배열의 합이 가장 큰 값을 찾는 알고리즘으로 kadane 알고리즘을 활용하면 된다

 

https://icodesiuuuu.tistory.com/12

Kadane’s Algorithm (카데인 알고리즘)

 

import java.util.*;
class Solution {
    static long max;
    public long solution(int[] sequence) {
        long answer = 0;
        max = 0;
        int[] a = sequence.clone();
        int[] b = sequence.clone();
        
        for(int i=0; i<sequence.length; i++) {
            if(i%2 == 0) {
                a[i] *= -1;
            } else {
                b[i] *= -1;
            }
        }
        kadane(a);
        kadane(b);
        return max;
    }
    
    public static void kadane(int[] arr) {
        long cur = 0;
        for(int i=0; i<arr.length; i++) {
            cur = Math.max(arr[i], cur+arr[i]);
            max = Math.max(cur, max);
        }
    }
}