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

2023-02-26 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