[PS] 백준 1912번 연속합

문제

예제

풀이

이 풀이를 참고하였다.
dp[i] = dp[i-1] + arr[i] 가 누적합 식이라는 건 쉽게 도출했지만 이식은 0~i번째까지 적용되고, 문제에서 원하는 k~i번째 연속합은 dp[i]-dp[k-1]이다.

'이 전까지의 연속합에서 현재 arr[i]를 더한 값과 현재 arr[i]를 비교하는데, 이 전까지의 연속합에서 arr[i]를 더한 값이 arr[i] 보다 작다면, 당연히 dp[i] = arr[i] 로 대체하는 것이 이득' -> 이부분을 전혀 떠올리지 못해서, 수열의 한자리(k) 씩 마다 k~i번째 연속합의 경우의 수를 모두 구하려다가 뭔가 이상한거 같아서 급히 풀이를 찾아보았는데 역시나 ㅠ

코드

.import java.io.IOException;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {

        Scanner in = new Scanner(System.in);

        int n = in.nextInt(); //수열의 크기

        int[] arr = new int[n];//값
        int[] dp = new int[n];        

        for(int i=0; i<n; i++) { //수열입력받기
            arr[i] = in.nextInt();
        }

        dp[0] = arr[0];
        int max = arr[0];

        for(int i=1; i<n; i++) {

            dp[i] = Math.max(dp[i-1] + arr[i], arr[i]);

            max = Math.max(max,  dp[i]);

        }
        System.out.println(max);

    }
}