😁 연속 구간의 최대 합 구하기
다양한 방법의 풀이 방법이 존재하는 주어진 배열에서 연속 구간의 최대 합 구하기 알고리즘을 Java
언어와 분할 정복으로구현하였으며 시간 복잡도는 O(nlgn)
이다.
예제로 풀이한 아래 코드에서 최대합은 14 로 결과가 나온다.
public class MaxNumber {
private static Integer [] numArrs = {-7,-1-2,0,10,4,-1};
private static List<Integer> numbers = Arrays.asList(numArrs);
private static Integer MIN = Collections.min(numbers);
public static void main(String[] args) {
System.out.println(maxSum(numArrs, 0,numArrs.length-1));
}
public static int maxSum(Integer [] numArrs,int start, int end){
/**
* 기저사례 구간의 길이가 1
*/
if(start == end) return numArrs[start];
int mid = (start + end) /2;
/**
* 두 부분에 걸쳐있는 최대의 합 구간을 찾기
*/
int left = MIN, right = MIN, sum =0;
for(int i= mid; i>=start; i--){
sum += numArrs[i];
left = Math.max(left, sum);
}
sum =0;
for(int j=mid+1; j<=end;j++){
sum += numArrs[j];
right = Math.max(right, sum);
}
/**
* 최대값이 한쪽에 생기는 부분 재귀호출
*/
int single = Math.max(maxSum(numArrs, start, mid), maxSum(numArrs, mid + 1, end));
// 두경우중 최대치를 반환
return Math.max(left + right, single);
}
}