[JAVA] 백준 1912번 【연속합】

---

이제 부분수열 구하는 문제는 해답이 잘 나오는 것 같다.

 

이 문제는, 누적합이 -값이 되지 않는한 게속해서 더해서 dp값에 저장하고, 음수가 되면 어떤수를 더해도, 안더하는게 이익인 상황이 되기 때문에, 누적합이 음수가 되는 해당 인덱스의 dp값을 0으로 입력시키게끔 구현하였다.

 

예제문제를 통해 살펴보도록 하자.

 

 

 

 

 

 

 

 

 

최종 dp배열은 위와 같이 생성되고, dp배열에서 가장 큰 원소를 추출하면 끝난다!

 

그리고 모든 원소가 0보다 작은 경우, 누적합의 최댓값은 원래 배열의 음수 원소들 중 가장 큰값이 된다.

 

이 부분에 유의하면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.valueOf(br.readLine());
		long[] dp = new long[N + 1];
		long[] array = new long[N + 1];
		String[] input = br.readLine().split(" ");

		for (int i = 1; i <= N; i++) {
			array[i] = Integer.valueOf(input[i - 1]);
		}
		
		dp[1] = array[1];

		for (int i = 1; i <= N; i++) {
			dp[i] = array[i] + dp[i - 1];
			if (dp[i] < 0) {
				dp[i] = 0;
			}
		}

		Arrays.sort(dp);
		Arrays.sort(array);
//		System.out.println(Arrays.toString(dp));
//		System.out.println(Arrays.toString(array));
		if (dp[N] == 0) {
			System.out.println(array[N - 1]);
		} else
			System.out.println(dp[N]);
	}
}