[Java] 정수형 배열에서의 부분 최대합 구하는 방법

2023-02-26

---

사진: Unsplash 의 BoliviaInteligente

---

1. 방법

 

아래와 같이 O(n)의 복잡도로 정수형 배열의 부분 최대합을 구할 수 있다. 음수가 나올 경우 현재의 합은 0으로 초기화되며, 매 순차마다 최댓값을 비교하여 설정해 주면 된다.

 

    public class Max {
        public static int sequence(int[] arr) {
            int nowSum = 0;
            int maxSum = 0;
            for(int i = 0; i < arr.length; i++){
                nowSum = Math.max(nowSum + arr[i], 0);
                maxSum = Math.max(maxSum, nowSum);
            }
            return maxSum;
        }
    }

---

메인 이미지 출처 : 사진: Unsplash의BoliviaInteligente