[백준/1912] 연속합

Baekjoon Online Judge - 1912

Review

• 이전까지 더한 값+현재값과 현재값을 비교해 더 큰 값이 DP[]에 들어가고, 이전까지의 최대값(max)과 현재의 DP[] 값을 비교해 더 큰 값이 max 변수에 들어가면 된다.
• 따라서 점화식은 DP[i] = max(DP[i-1] + A[i], A[i])
• 그런데… 왜 맞는데… 틀리지?
• 그건 내가 max 변수의 값을 0으로 초기화했기 때문임
• 초기화 잘못해서 네 번 틀린 사람 나야 나 나야 나

Code (JAVA)

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

public class Main {
  
  public static void main(String args[]) throws IOException{
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(bf.readLine());
    int[] DP = new int[N + 1];
    int[] A = new int[N + 1];
    int max;
    StringTokenizer st = new StringTokenizer(bf.readLine());
    
    for(int i = 1; i <= N; i++) {
      A[i] = Integer.parseInt(st.nextToken());
    }

    DP[1] = A[1];
    max = A[1];
    
    for(int i = 1; i <= N; i++) {
      DP[i] = Math.max(DP[i - 1] + A[i], A[i]);
      max = Math.max(max, DP[i]);
    }
    
    System.out.println(max);
  }
  
}