최대 하위 배열 의 합

문제 설명
n 개의 요 소 를 포함 하 는 정수 배열, 배열 요 소 는 양수 일 수도 있 고 마이너스 일 수도 있 습 니 다. 배열 에서 연속 되 는 하나 이상 의 요 소 는 배열 을 바 꾸 는 서브 배열 이 라 고 부 릅 니 다. 서브 배열 의 모든 요 소 를 합 쳐 서브 배열 과 라 고 부 르 고 정수 배열 의 서브 배열 과 최대 치 를 구 합 니 다.예 를 들 어 배열 array = {1, - 2, 4, - 3, 5, - 6} 은 배열 array 의 최대 하위 배열 과: 4 + (- 3) + 5 = 6 이다.
분석 구 해
방법 1: 만력 법
가장 쉽게 생각 할 수 있 고 가장 간단 한 생각 은 이 배열 의 모든 하위 배열 을 옮 겨 다 니 며 가장 큰 하위 배열 의 합 을 비교 하 는 것 이다.사고방식 은:
하위 시퀀스 길이 가 1 인 모든 하위 배열 은 n 개: {a0}, {a1}, ·, {an} 이 있 습 니 다.
하위 시퀀스 길이 가 2 인 모든 하위 배열 은 n - 1 개: {a0, a1}, {a1, a2}, · ·, {an - 1, an}
···
하위 시퀀스 길이 n 의 모든 하위 배열 은 1 개 입 니 다: {a0, a1, ·, an}
알고리즘:

	/**
	 * get max sum of an array's subsequence by Brute Force.
	 */
	public static int getMaxSubArrayBF(int[] array) {
		int maxSum = Integer.MIN_VALUE;
		int tmpSum = 0;
		/**
		 * i :      
		 * j :        
		 */
		for (int i = 1; i <= array.length; i++) {
			for (int j = 0; j < array.length - i + 1; j++) {
				tmpSum = 0;
				for (int k = 0; k < i; k++) {
					tmpSum += array[j + k];
					if(maxSum < tmpSum)
						maxSum = tmpSum;
				}
			}
		}
		return maxSum;
	}

알고리즘 시간 복잡 도 는 O (n ^ 3) 입 니 다.
방법 2: 만력 법 개선
방법 중 가장 뚜렷 한 단점 중 하 나 는 중복 계산 이다. 예 를 들 어 sum [i, j] = sum [i, j - 1] + array [j] 이다. 즉, 비교적 긴 하위 배열 과 비교적 짧 은 하위 배열 을 사용 하기 때문에 하위 배열 의 합 을 계산 할 때 이미 계 산 된 하위 배열 의 합 을 반복 적 으로 이용 하여 시간 복잡 도 를 줄 일 수 있다.
알고리즘:

	/**
	 * get max sum of an array's subsequence by Majorizing Brute Force.
	 */
	public static int getMaxSubArrayMBF(int[] array) {
		int maxSum = Integer.MIN_VALUE;
		int tmpSum = 0;
		// i :        
		// j :        
		for (int i = 0; i < array.length; i++) {
			tmpSum = 0;
			for (int j = i; j < array.length; j++) {
				tmpSum += array[j];
				if(maxSum < tmpSum)
					maxSum = tmpSum;
			}
		}
		return maxSum;
	}

만력 법 이지 만 알고리즘 시간 복잡 도 는 O (n ^ 2) 입 니 다.
방법 3: 동적 기획
동적 계획 의 방법 으로 이 문 제 를 해결 할 수 있 습 니 다. 먼저 배열 의 마지막 요소 인 array [n - 1] 를 예 로 들 어 가장 큰 하위 배열 과 의 관 계 를 설명 하고 두 가지 상황 이 있 습 니 다.

가장 큰 하위 배열 은 요소 array [n - 1] 를 포함 합 니 다. 즉, 가장 큰 하위 배열 은 요소 array [n - 1] 로 끝 납 니 다.

최대 하위 배열 은 요소 array [n - 1] 를 포함 하지 않 습 니 다. 그러면 array [0, 1, ·, n - 1] 의 최대 하위 배열 문 제 는 바로 하위 배열 array [0, 1, ·, n - 2] 의 최대 하위 배열 문 제 를 구 하 는 것 입 니 다.

상기 분석 을 통 해 알 수 있 듯 이 여기 서 문 제 를 규모 가 작은 같은 유형의 서브 문제 로 분해 할 수 있 고 규모 가 큰 문 제 는 규모 가 작은 문제 의 결 과 를 사용 할 수 있 으 며 동태 적 인 계획 사상 을 사용 할 수 있다.
기수 그룹 array [0, 1, · ·, i - 1] 에는 엔 딩 요소 array [i - 1] 의 가장 큰 단락 배열 과 endMaxSum [i - 1] 이 포함 되 어 있 습 니 다. 요소 array [i - 1] 가 반드시 포함 되 어 있 기 때문에 endMaxSum 은 array [i - 1] 을 포함 하 는 키 배열 이거 나 단독 요소 array [i - 1] 로 구 성 된 하위 배열 입 니 다. 따라서:
endMaxSum[i - 1] = max{endMaxSum[i - 2] + array[i-1] , array[i - 1]}
배열 array [0, 1, ·, i - 1] 의 최대 하위 배열 과 tmp MaxSum [i - 1] 을 계산 했다 고 가정 하면 배열 array [0, 1, ·, i] 의 최대 하위 배열 과:
tmpMaxSum[i] = max{endMaxSum[i] , tmpMaxSum[i - 1]}
알고리즘:

	/**
	 * get max sum of an array's subsequence by Dynamic Programming
	 */
	public static int getMaxSubArrayDP(int[] array) {
		int[] endMaxSum = new int[array.length];
		int[] tmpMaxSum = new int[array.length];
		
		endMaxSum[0] = tmpMaxSum[0] = array[0];
		
		for (int i = 1; i < array.length; i++) {
			endMaxSum[i] = max(endMaxSum[i - 1] + array[i], array[i]);
			tmpMaxSum[i] = max(endMaxSum[i], tmpMaxSum[i - 1]);
		}
		return tmpMaxSum[array.length - 1];
	}
	
	private static int max(int a, int b) {
		return a > b ? a : b;
	}

알고리즘 시간의 복잡 도 는 O (n) 이다.이 알고리즘 은 endMaxSum [i - 1] 에 두 가지 특징 이 있 습 니 다. 반드시 엔 딩 요소 인 array [i - 1] 를 포함 하고 연속 적 인 하위 배열 (하나의 요소 도 하위 배열 을 구성 할 수 있 습 니 다) 이 어야 합 니 다.
방법 4: 동적 계획 개선
방법 세 가지 단점 이 있 습 니 다. 첫 번 째 는 n 길이 의 배열 endMaxSum 과 tmp MaxSum 을 사용 하여 공간 소 비 를 증가 하 는 것 입 니 다.두 번 째 는 최대 하위 배열 의 합 만 계산 할 수 있 을 뿐 최대 하위 배열 의 위 치 를 얻 을 수 없다 는 것 이다.분석 방법 3 의 두 공식 을 통 해 개선 방향 을 쉽게 얻 을 수 있다.
알고리즘:

	/**
	 * get max sum of an array's subsequence by Majorizing Dynamic Programming
	 */
	public static int getMaxSubArrayMDP(int[] array) {
		int startPos = 0;
		int endPos = 0;

		//        tmpMaxSum
		int maxSum = array[0];
		//        endMaxSum
		int endMaxSum = array[0];
		
		for (int i = 1; i < array.length; i++) {
			if(endMaxSum > 0) {
				endMaxSum = endMaxSum + array[i];
				if(endMaxSum > maxSum) {
					maxSum = endMaxSum;
					endPos = i;
				}
			}
			else {
				endMaxSum = array[i];
				if(endMaxSum > maxSum) {
					maxSum = endMaxSum;
					startPos = i;
					endPos = i;
				}
			}
		}
		System.out.println("From " + startPos + " to " + endPos);
		return maxSum;
	}

알고리즘 시간 복잡 도 는 여전히 O (n) 이지 만 공간 복잡 도 는 O (1) 로 낮 아 지고 최대 하위 배열 의 위 치 를 얻 을 수 있다.
총결산
동적 계획 법 (Dynamic Programming) 은 분 치 법 과 유사 해 문 제 를 규모 가 점점 줄 어드 는 같은 유형의 하위 문제 로 층 층 이 분해 하 는 것 이다.그 와 분 치 법의 중요 한 차이 점 은 분 치 법 으로 분해 한 후에 얻 은 서브 문 제 는 보통 서로 독립 되 고 동태 규범 으로 분해 한 후에 얻 은 서브 문 제 는 대부분이 중복 된다 는 것 이다.각 키 문제 가 서로 독립 되 기 때문에 분 치 법 은 재 귀적 호출 이 발생 하여 중복 계산 을 피한다. 동태 계획 법 은 보통 전달 하 는 방법 을 사용한다. 규모 가 가장 작은 서브 문제 부터 계산 하고 규모 가 점점 커지 는 서브 문 제 를 순서대로 계산한다. 큰 서브 문 제 를 계산 할 때 작은 규칙 적 인 문제 의 결 과 를 사용 해 야 하기 때문이다.따라서 매번 계산 이 끝 난 후에 얻 은 결 과 를 보존 하고 이 방법 에 따라 계산 규 모 를 계속 확대 하여 원 하 는 문제 의 규모 에 이 를 때 까지 해 야 한다.
만약 에 한 문제 가 몇 개의 고도 로 중복 되 는 서브 문제 로 분 해 될 수 있 고 문제 도 가장 좋 은 서브 구조 적 특성 을 가지 면 동적 계획 법 으로 구 해 를 하고 전달 하 는 방식 으로 최 적 치 를 계산 하 며 필요 한 정 보 를 기록 할 수 있다. 마지막 으로 기 록 된 정보 구조 에 따라 최 적 화 를 할 수 있다.문제 풀이 절 차 는 다음 과 같이 요약 할 수 있다.

가장 좋 은 성질 을 찾아내 고 그 구조 적 특성 을 묘사한다.

최 적 화 된 값 을 재 귀적 으로 정의 합 니 다 (동적 계획 방정식 을 작성 합 니 다).

바닥 에서 위로 (규 모 는 작은 것 에서 큰 것 까지) 전달 방식 으로 최 적 치 를 계산한다.

최 우수 치 를 계산 할 때 얻 은 정보 에 따라 재 귀 방법 으로 최 적 화 를 구성한다.