연속부분최대합L

문제

---

N개의 정수가 주어질 때, 연속된 부분을 선택하여 합을 최대화 하는 프로그램을 작성하시오. 예를 들어, 아래와 같이 8개의 숫자가 있을 경우, 색칠된 부분을 선택했을 때 그 합이 가장 최대가 된다.

 

입력

---

첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 1,000,000 ) 두 번째 줄에 n개의 정수가 주어진다.  

출력

---

연속된 부분을 선택하였을 때의 최댓값을 출력한다.

 

예제 입력

8
2 3 -5 8 -3 4 2 -9

예제 출력

11

 

예제 입력

5
-1 -2 3 -2 4

예제 출력

5

 

---

연속부분최대합을 동적계획법으로 푸는 풀이다.

Table(i) 를 i번째 수를 오른쪽 끝으로 하는 연속부분 중 최대합이라고 정의한다.

그러면 Table에 대한 점화식은 Table(i) = max ( Table(i-1) + Data(i) , Data(i) ) 가 된다.

위의 예제로 Table 을 구해보면 2  5  0  8  5  9  11  2 이므로, 이 값들중 가장 최대값인 11이 정답이 된다.

그러면 연속부분최대합을 완전 탐색법에서는 O(n^2) 분할 정복법에서는 O(nlogn) 동적계획법에서는 O(n) 만에 구할 수 있다.

	import java.util.Scanner;
	public class SumRangeMaxL {
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int [] arr = new int[n];
	int [] Table = new int[n];
	for(int i=0; i<n; i++) {
	arr[i]=sc.nextInt();
	}
	Table[0] =arr[0];
	for(int i=1; i<n; i++) {
	if(Table[i-1] + arr[i] > arr[i]) Table[i] = Table[i-1] + arr[i];
	else Table[i] = arr[i];
	}
	int max = Table[0];
	for(int i=0; i<n; i++) {
	if(Table[i] > max) max = Table[i];
	}
	System.out.println(max);
	}
	}

view raw SumRangeMaxL.java hosted with ❤ by GitHub