티스토리 뷰

문제 . 1차원 배열에서 연속된 부분 구간 중 그 합이 최대인 구간을 찾는 문제.


예) 배열 [-7, 4, -3, 6, 3, -8, 3, 4] 에서 최대 합을 갖는 부분 구간은 [4, -3, 6, 3] 으로 합은 10 이다


그냥 생각 같아선 다음과 같이 구할 수 있지만, 반복문이 3개이기 때문에 O(N^3)의 시간 복잡도가 걸리기 때문에 좋지 않다.

	private int inefficientMacSum(int[] arr) {
		int N = arr.length;
		int ret = 0;
		for(int i =0; i< N ; i++) {
			for(int j = i; j< N; j++) {
				// A[i,j] 의 합
				int sum = 0;
				for (int k=i; k <=j; ++k) {
					sum += arr[k];
				}
				ret = Math.max(ret, sum);
			}
		}
		return ret;
	}


이를 개선하여 O(N)번 수행하는 반복문이 두개로 바꾸어 보자 = 시간복잡도는 O(N^2)

	private int betterMaxSum(int[] arr) {
		int N = arr.length;
		int ret = 0;
		for (int i = 0; i < N; i++) {
			int sum = 0;
			for (int j = i; j < N; j++) {
				sum += arr[j];
				ret = Math.max(ret, sum);
			}
		}
		return ret;
	}


마지막으로 동적 계획법을 이용하여 구현하면 시간복잡도는 O(N)이 된다.

	private int fasttestMaxSum(int[] arr) {
		int N = arr.length;
		int ret = 0;
		int psum = 0;
		for (int i = 0; i < N; i++) {
			psum = Math.max(psum, 0) + arr[i];
			ret = Math.max(psum, ret);
		}
		return ret;

	}

직접 해보면

arr []= [-7, 4, -3, 6, 3, -8, 3, 4]


i = 0일 때

psum = max(0, 0) -7 = -7

ret = max(-7,0) = 0


i = 1 일 떄

psum = max(-7,0) + 4 = 4

ret = max(4,0) = 4


i = 2 일 떄

psum = max(4,0) + -3 = 1

ret = max(1,4) = 4


i = 3 일 때

psum = max(1,0) + 6 = 7

ret = max(7,4) = 7


i = 4 일 때

psum = max(7,0) + 3 = 10

ret = max(10,7) = 10


i=4 일 때

psum = max(10,0) -8 = 2

ret = max(2,10) = 10


i=5 일 떄

psum = max(2,0) +3 = 5

ret = max(5,10) = 10


i=6일 때

psum = max(5,0) +4 = 9

ret = max(9,10) = 10


즉 N번 수행하여 10이라는 값을 얻을 수 있음

'알고리즘' 카테고리의 다른 글

분할정복  (0) 2016.08.04
재귀 함수  (0) 2016.07.29
댓글
댓글쓰기 폼
공지사항
최근에 달린 댓글
Total
66,013
Today
0
Yesterday
10
TAG
more
«   2022/12   »
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
글 보관함