[백준] 1912 연속합

문제

• 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

  문제풀이

• brute-force 를 풀었을 때, O(n 제곱)
• 중복되는 부분을 memorization 을 사용해서 처리.

왜 문제를 풀지 못했는가? 어떤 부분을 생각하지 못했는가?

• Source

  public class Num1912 {
    private static int[] num;
    private static int[] cache;
  
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        num = new int[n];
        cache = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = scan.nextInt();
        }
  
        System.out.println(solve());
    }
  
    public static int solve() {
        /**
         *     Sol1. brute-force
         *     1. O(n 제곱)
         *
         *  Sol2. memorization 
         */
        int max = Integer.MIN_VALUE;
        for (int i = num.length - 1; i >= 0; i--) {
            max = Math.max(max, solve(i));
        }
        return max;
    }
  
    public static int solve(int start) {
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = start; i < num.length; i++) {
            if (cache[i] != 0) {
                sum += cache[i];
                max = Math.max(max, sum);
                break;
            } else {
                sum += num[i];
                max = Math.max(max, sum);
            }
        }
        return cache[start] = max;
    }
  

}