백준 1912 자바 - 연속합

문제

---

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

1912번: 연속합

 

 

 

 

문제해결

---

- dp 배열을 만들어 반복문을 돌면서 i번째 까지의 연속합 중 가장 큰 값을 dp배열에 담는다

- dp 배열 중 가장 큰 값이 연속합 중 가장 큰 값이 된다

- 맨 첫번째 숫자의 연속합은 자기 자신이므로 dp[0] = arr[0]으로 초기화 해준다

 

- 예제 1번의 수열일때

10 -4 3 1 5 6 -35 12 21 -1

dp 배열: [10, 6, 9, 10, 15, 21, -14, 12, 33, 32]

이렇게 i번째 숫자의 가장 큰 연속합이 dp 배열에 담겨있고 dp배열중 가장 큰 값이 33이므로 답은 33이 된다

import java.util.Scanner;

public class B1912_2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int[] dp = new int[n];
        // 맨 첫번째 숫자의 연속합은 자기 자신
        dp[0] = arr[0];
        //dp 배열에 i번째 연속합 중 가장 큰 값을 넣는다
        for (int i = 1; i < n; i++) {
            //i-1까지의 연속합 + i번째 숫자 or i번째 숫자 중 가장 큰 값이 dp[i]
            dp[i] = Math.max(arr[i], dp[i-1] + arr[i]);
        }
        
        //가장 큰 연속합 찾기
        int max = dp[0];
        for (int i = 1; i < n; i++) {
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
}