[알고리즘-JAVA] 백준 알고리즘 1912번 - 연속합

접근 과정
1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

주어진 임의의 수열에서 연속합의 최대값 구하기

2. 나의 방식대로 문제를 재정의 하자.

d[i] = i번째 수를 마지막으로 했을 때의 최대 연속합

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

bottom-up을 이용한 dp

4. 어떻게 계산할 것인가?
1) 입력

Scanner사용

 

2) 시간 복잡도 계산

n만큼만 돌면 되고 하나의 n을 구할때의 연산은 O(1)이므로

O(N)이다.

5. 주의할 점은 무엇인가?

최대값을 구할때 마이너스가 나올수도 있다는 점.

 

6. 풀이 과정

a[i]로 끝나는 최대 연속합

경우 1. A[i-1]로 끝나는 연속합을 포함하는 경우 = D[i-1]+A[i]

경우 2. 새로운 연속합 A[i]

 

[전체 소스 코드]

 

아래는 처음에 틀렸던 코드.

평소와 같이 max를 찾아낸다고 생각했지만, 여기서는 정답이 음수가 나올 수 있다는것을 까먹었다..

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static int d[];
    public static int arr[];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        d = new int[count];
        arr = new int[count];
        for (int i = 0; i < count; i++){
            arr[i] = sc.nextInt();
        }
        d[0] = arr[0];
        for (int i = 1; i < count; i++){
            d[i] = Math.max(arr[i],d[i-1]+arr[i]);
        }
        int max = 0;
        for (int i = 0; i < count; i++){
            if (d[i] > max){
                max = d[i];
            }
        }
        System.out.println(max);
    }
}

처음에 틀렸던 곳을 고쳐내고

정답이 음수가 나올 수 있게끔 d[0]값을 초기값으로 설정해주었다.

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static int d[];
    public static int arr[];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        d = new int[count];
        arr = new int[count];
        for (int i = 0; i < count; i++){
            arr[i] = sc.nextInt();
        }
        d[0] = arr[0];
        for (int i = 1; i < count; i++){
            d[i] = Math.max(arr[i],d[i-1]+arr[i]);
        }
        int max = d[0];
        for (int i = 1; i < count; i++){
            if (d[i] > max){
                max = d[i];
            }
        }
        System.out.println(max);
    }
}