[백준-1912]-[다이나믹프로그래밍] - 연속합

문제경로 : https://www.acmicpc.net/problem/1912

이문제는 굉장이 간단하게 접근 할 수 있다. 

제공된 예제를 바탕으로 문제를 풀어보자.

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

총 10개의 정수가 제공 되고 연속된 구간의 합 중에서 제일 큰 값이 무엇인지 출력해주면 된다.

출력은 33이 출력이 돼야 한다.

이문제를 간단하기 풀기 위해선 배열의 크기를 입력받은 사이즈 보다 한칸 더 크게 생성하면 쉽고 짧게 풀 수 있다.

첫번째 입력을 배열의 인덱스 0에 저장하지 말고 1에 저장하면 된다. 

이문제를 풀기위해 필요한 변수는 구간합의 최대값을 저장하는 max 라는 변수와 입력받은 값들을 저장할 long 타입의 일차원 배열만 있으면 풀 수 있다. 

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();            // 수를 입력받을 횟수
        
        long max = Long.MIN_VALUE;          // 구간합의 최대값을 저장할 변수
        long[] arr = new long[num+1];    // 입력받은 수 또는 구간합을 저장할 long 타입 일차원 배열
    }

문제를 푸는 방법은 입력받은 횟수만큼 반복을 하면서  현재 인덱스에 입력받은 수와 이전 인덱스의 값의 합이 현재 입력 받은 수보다 크면 현재 인덱스에 값을 저장하고 

그 값이 max 보다도 크면 max의 값까지 변경해주면 된다.

        for(int i=1; i <= num; i++) {
            arr[i] = sc.nextLong();
            // 구간합 구하기            
            if(arr[i] + arr[i-1] > arr[i]) arr[i] = arr[i] + arr[i-1];
            // 현재 구간합이 max보다 크면 max 값 변경하기
            if(arr[i] > max) max = arr[i];
        }
        
    }

여기서 제일 중요한 것이 있는데 반복도 아니고 조건도 아닌 max 값의 초기 값이다.

max의 값을 0으로 초기화 한다면 모든 수가 음수로 입력 됐을때 출력이 0이 된다. 

소스

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();            // 수를 입력받을 횟수
        
        long max = Long.MIN_VALUE;          // 구간합의 최대값을 저장할 변수
        long[] arr = new long[num+1];    // 입력받은 수 또는 구간합을 저장할 long 타입 일차원 배열
 
        for(int i=1; i <= num; i++) {
            arr[i] = sc.nextLong();
            // 구간합 구하기            
            if(arr[i] + arr[i-1] > arr[i]) arr[i] = arr[i] + arr[i-1];
            // 현재 구간합이 max보다 크면 max 값 변경하기
            if(arr[i] > max) max = arr[i];
        }
        System.out.println(max);
    }