백준 1912번 연속합 <S2> - 수학

 

수학 구현 문제네오, 유의할 점은 숫자 배열에따라 길게 가져가는게 이득일 수도 있네오

예제 2 입력처럼

2 1 -4 3 4 -4 6 5 

가 있으면 2부터 5까지 전부 더하는게 더 큰 경우가 생기듯 더했을때 생기는 이점을 고려하면서 짜면 될듯 합니다.

dp를 사용해서 인덱스마다 값을 정해서 Math.max 비교로 해도 되겠네오

 

또 왤케 틀렸어.. 테스트 좀 제대로

 

실수를 했었고만 꼴꼴

 

import java.util.*;
 
public class Main { // 1912. 연속합 35%
 
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();    
        int[] arr = new int[n];
        // Input
        for (int num = 0; num < n; num++) {            
            arr[num] = sc.nextInt();            
        }
        int [] dp = new int [n];
        dp[0] = arr[0];
        int max = dp[0];
        // Logic
        for(int i = 1; i<n; i++) { // i별 최대값을 저장.
            dp[i] = Math.max(arr[i], dp[i-1] + arr[i]); // i-1 최대값 + 다음값이랑 현재값 비교
            max = Math.max(dp[i], max);
        }
        
        // Output
        System.out.println(max);
 
        sc.close();
    }// main
}// solution