[백준 java] 1912 - 연속합

1912번: 연속합

---

구해야 하는 것은 연속되는 수의 합중 최대값을 구해야한다.

예제 2와 같이 음수가 들어가도 최대값이 나오는 경우는 있다.

 

만약 음수를 더해도 연속 수 합의 결과값이 양수라면 ( 3 +4 - 4 +6 +5) 최대값이 된다

 

dp에는 i 이전 까지의 합과 더해야 할 값( arr[i] ) 중 더 큰값이 저장된다

10
2 1 -4 3 4 -4 6 5 -5 1

다음 예제를 보면

 

dp[3] = -1

 

dp[4] = Math.max ( dp[3]+ 3 , 3 )

-> -1 + 3 과 3중 더큰 3이 저장된다

 

dp[4] = Math.max ( dp[3]+ 4 , 4 )

 

dp[5] = Math.max ( dp[4] -4 , -4 )  

-> 3과 -4중 더큰 3이 저장된다.

 

dp[6] =  Math.max ( dp[5]+ 6 , 6 )

-> 이전에 음수를 더했어도 양수값이 나왔으니 무조건 더하면 더 크다

 

즉 dp[i] 에는 ( dp[i-1] + arr[i] ) 와 arr[i] 중 더 큰값이 저장되는 것이다.

---

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

public class B1912 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] board  = new int[N+1];
        int[] dp = new int[N+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            board[i] = Integer.parseInt(st.nextToken());
        }

        int res = board[1];
        dp[1] = board[1];

        for (int i = 2; i <= N; i++) {
            dp[i] = Math.max(dp[i-1] + board[i], board[i]);
            System.out.println(dp[i]);
            if (dp[i] > res) res = dp[i];
        }
        System.out.println(res);
    }
}

입력값 수를 1000으로 잘못보고 while문으로 전체 합을 비교해서 시간초과가 났다...