최대구간합 구하기 java 버전

아래와 같은 문제가 있습니다.

 

문제)

[-7, 4, -3, 6, 3, -8, 3, 4,-2] 와 같은 배열이 있다.

이 때 배열 내 부분 최대합을 구하라.

 

답)

4 - 3 + 6 + 3 = 10

[출처] [알고리즘] 동적 계획법을 활용한 배열 내 부분 최대 합 구하기|작성자 Jackson OH

 

이를 프로그램으로 구현하기 위한 방법은 여러가지가 있습니다.

 

그 중 가장 단순한 방법으로 루프를 이용해  최고값을 찾아내는 방법이 있습니다.  아래 예제는 마이너스 최대값은 0으로 표시합니다.

 

private static int getMaxSumSq(int[] arrn) { int block = 1; int sidxs = 0; int sidx = 0; int eidx = 0; int max =0; //최대 값 int maxb =0; //계산값 while(sidxs < arrn.length){ if(arrn[sidxs]>0) break; sidxs++; } while(block <= arrn.length){ sidx = sidxs; eidx = sidx+block; //sidx + 1부터 시작 maxb=0; for(int i=0; i<block; i++){ maxb += arrn[i]; } if(maxb>0 && maxb>max){ max = maxb; } while(eidx < arrn.length){ maxb -= arrn[sidx]; maxb += arrn[eidx]; if(maxb>0 && maxb>max){ max = maxb; } eidx++; sidx++; } block++; } return max; }

 

위와같이 반복문 안에 다 시 반복문  형식으로 모든 경우의 수를 비교하는방법은  O(N^2) 의 시간복잡도를 가지게 됩니다.

 

아래는  O(N^2) 의 시간 복잡도를 줄이기 위한 방법으로 배열을 절반으로 나눠 재귀호출을 이용한 방법입니다.

 

  private static int getMaxSum(int[] arrn, int lo, int hi) { // 기저 사례: 구간의 길이가 1일 경우 if(lo == hi) return Math.max(arrn[lo], 0); // 배열을 A[lo..mid], A[mid+1..hi]의 두 조각으로 나눈다. int mid = (lo + hi) / 2; // 두 부분에 모두 걸쳐 있는 최대 합 구간을 찾는다. 이 구간은 // A[i..mid]와 A[mid+1..j] 형태를 갖는 구간의 합으로 이루어진다. // A[i..mid] 형태를 갖는 최대 구간을 찾는다. int left = 0, right = 0, sum = 0; for(int i = mid; i >= lo; --i) { sum += arrn[i]; left = Math.max(left,sum); } // A[mid+1..j] 형태를 갖는 최대 구간을 찾는다. sum = 0; for(int j = mid+1; j <= hi; ++j) { sum += arrn[j]; right = Math.max(right,sum); } // 최대 구간이 두 조각 중 하나에만 속해 있는 경우의 답을 재귀 호출로 찾는다. int single = Math.max(getMaxSum(arrn, lo, mid),getMaxSum(arrn, mid+1, hi)); // 두 경우 중 최대치를 반환한다. return Math.max(left + right, single) ; }

 

마지막으로  동적 계획법을 사용하여 선형(N)의 시간복잡도를 갖도록 처리한 프로그램입니다.

 

  private static int getMaxSum(int[] arrn) { int psum = 0, max = 0; for(int i = 0; i<arrn.length; i++) { psum = Math.max(psum, 0) + arrn[i]; max = Math.max(psum, max); } return max; }

 

간단히 설명하면

 

최대값 max , 구간 합 psum

 

1.루프를 실행하면서 psum 에 값을 더해주고 max에는 psum 중 최대값을 저장한다.

2. psum 이 0 보다 작아지면 0으로 설정한다.

예를 들면
숫자 : [3 , 5,-4,1,-7, 2, 8,-3, 5,-1]
sum : [3 , 8, 4, 5, 0, 2,10, 7,12,11]
max : [3 , 8, 8, 8, 8, 8,10,10,12,12]

이렇게 됩니다.