[JAVA]백준_1912_연속합

문제링크

https://www.acmicpc.net/problem/1912

1912번: 연속합

 

 

 

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		int arr[] = new int [N];
		int d[] = new int[N];
		int result = 0;
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) arr[i] = Integer.parseInt(st.nextToken());
		
		Arrays.fill(d, Integer.MIN_VALUE);
		d[0] = arr[0];
		result = d[0];
		
		for(int i=1;i<N;i++) {
			d[i] = Math.max(d[i-1]+arr[i], arr[i]);
			result = Math.max(result, d[i]);
		}
		
		System.out.println(result);
	}
}

 

처음 접근 하였을 때는 d[i] = d[i-1]+arr[i]해서  d[i]<d[i-1] 하면 다시 시작해주는 방향으로 잡고 풀었으나 이렇게 풀 시에는

이 테스트 케이스가 제대로 나오지않는다.

 

따라서 생각해본 결과

계속 더하다가 만약 d[i] = d[i-1] + arr[i] 인데 이 값이 만약 arr[i]보다 작다면 그 이전 부분은 다 버리고 arr[i]부터 시작해도 된다. 

그리고 max 값은 d[N]번째가 max값이 되는 것이 아니라 따로 변수 하나를 선언해주어서 d[i]와 최대값을 담는 변수 중 최대값을 계속 비교해주었다.