[백준] 1912 연속합 (미해결)

1912번: 연속합

처음에는 쉬운데 정답률이 왜 27%밖에 안 되지? 하고 쉽게 풀었다.

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        ArrayList list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(in.nextInt());
        }
        int[][] arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(i < j)
                    continue;
                if(i == j)
                    arr[i][j] = list.get(j);
                else {
                    arr[i][j] = arr[i-1][j] + list.get(i);
                }
            }
        }
        int max = arr[0][0];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(i < j) continue;
                if (arr[i][j] > max) {
                    max = arr[i][j];
                }
            }
        }
        System.out.println(max);
    }
}

이렇게 제출했더니 메모리 초과가 났다.

 

그래서 아 동적계획법은 생각보다 메모리를 아껴쓸 수가 있지? 하고

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] list = new int[n];
        for (int i = 0; i < n; i++) {
            list[i] = in.nextInt();
        }
        int[] arr = new int[n];
        int max = list[0];
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i == j) arr[j] = list[i];
                else arr[j] = arr[j - 1] + list[j];
                if(arr[j] > max) max = arr[j];
            }
        }
        System.out.println(max);
    }
}

이렇게 했더니 시간초과가 났다.

꼭 내 손으로 풀어낼거다.