★ 백준/1912 연속합 / 다이나믹 프로그래밍,메모이제이션

연속합 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (추가 시간 없음)

128 MB

114189

40905

28810

34.544%

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

33

예제 입력 2 복사

10
2 1 -4 3 4 -4 6 5 -5 1

예제 출력 2 복사

14

예제 입력 3 복사

5
-1 -2 -3 -4 -5

예제 출력 3 복사

-1

---

풀이

/*
n개의 수가 주어지고, 그 숫자들중 연속된 몇개 수를 선택해서 최대값을 구한다. 최소 한개 이상 선택해야한다.
정수의갯수는 최대 10만개, 10만개를 1개뽑는,2개뽑는...n개뽑는 조합을 모두구해서 최대값을 구하면 무조건 시간초과 조합 -> O(2^n)
해당 위치의 숫자와, 그 숫자를 더했을때 어떤값이 더큰지 체크한다, 그렇게함으로서 그 숫자를 선택하지않았을때와, 그 숫자를 선택했을 2경우의 최대값을 체크할 수 있다.
각 숫자에 도착했을때 뽑고,안뽑고의 둘중 최대값을 구해보는것이므로 모든경우를 확인한다고 볼 수 있다.(연속된 수를 뽑는 문제니까)
 */

메모이제이션 해야하는 구간을 잘생각하는게 어려웠다.

sums라는 dp배열을 구현해서 푼느낌

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    /*
    n개의 수가 주어지고, 그 숫자들중 연속된 몇개 수를 선택해서 최대값을 구한다. 최소 한개 이상 선택해야한다.
    정수의갯수는 최대 10만개, 10만개를 1개뽑는,2개뽑는...n개뽑는 조합을 모두구해서 최대값을 구하면 무조건 시간초과 조합 -> O(2^n)
    해당 위치의 숫자와, 그 숫자를 더했을때 어떤값이 더큰지 체크한다, 그렇게함으로서 그 숫자를 선택하지않았을때와, 그 숫자를 선택했을 2경우의 최대값을 체크할 수 있다.
    각 숫자에 도착했을때 뽑고,안뽑고의 둘중 최대값을 구해보는것이므로 모든경우를 확인한다고 볼 수 있다.(연속된 수를 뽑는 문제니까)
     */

    static int n;
    static int[] numbers;
    static int[] sums;
    static int max = Integer.MIN_VALUE;


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

        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        n = Integer.parseInt(br.readLine());
        numbers = new int[n];
        sums = new int[n];
        String[] input = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            numbers[i] = Integer.parseInt(input[i]);
        }
    }

    static void solve() throws IOException {
        int tempSum = numbers[0];
        sums[0] = numbers[0];
        for (int i = 1; i < n; i++) {
            int tempMax = Math.max(numbers[i], numbers[i] + tempSum); //해당 위치의 숫자와, 그 숫자를 더했을때 어떤값이 더큰지 체크한다.
            sums[i] = tempMax;
            tempSum = tempMax;
        }

        for (int i = 0; i < n; i++) {
//            System.out.println("sums = " + sums[i]);
            max = Math.max(max, sums[i]);
        }
        bw.write(max+"");

    }


}

 

참고

https://st-lab.tistory.com/140