📌 문제

[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보다 작거나 같은 정수이다.

⬆️ 출력

첫째 줄에 답을 출력한다.

💡 코드

⌛ 시간 초과 : 메모이제이션을 써먹긴 해야 될 것 같은데 어떻게 써야할 지 감이 안와서 일단 고전 방식으로 돌파,, 사실 풀 때까지만 해도 앞전 결과를 sum에 저장하니까 나름 메모이제이션 아닌가? ㅎ 라는 생각을 했으나 일단 근본이 이중 for문이라 그런가 시간 초과가 발생하였다,,

import java.io.*;
import java.util.*;
public class Main {
	
	static int[] memo;
	static int[] arr;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		arr = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int result = cal(n);
		bw.write(result + "");
		
		br.close();
		bw.close();
	}
	
	static int cal(int n) {
		int max = Integer.MIN_VALUE;
		
		while(n > 0) {
			int sum = 0;
			
			for(int i=n-1;i>0;i--) {
				sum += arr[i];
				max = Math.max(max, sum);
			}
			
			n--;
		}
		return max;
	}
}

✅ i번째까지의 최대 합은 i-1번째까지 구할 수 있는 최대합에 i번째의 값을 더한 값과, 그냥 i번째 값 하나를 비교하였을 때 더 큰 쪽이라고 할 수 있다.

첫번째까지의 최대합 memo[0]은 첫번째 값과 같으므로 arr[0]을 대입해주고, 최댓값 max 또한 같은 값을 대입해준다. 이후, i-1번째까지의 최대합에 i번째 수를 더한 값 memo[i-1]+ arr[i]과 i번째 수 arr[i]를 비교하여 더 큰 값을 다음에 넘겨줄 최대합 memo[i]에 저장하고, memo[i]와 기존의 최댓값 max 중 더 큰 값을 max에 담는다.

import java.io.*;
import java.util.*;
public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		int[]  arr = new int[n];
		Integer[] memo = new Integer[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		memo[0] = arr[0];
		int max = arr[0];
		
		for(int i=1;i<n;i++) {
			memo[i] = Math.max(memo[i-1] + arr[i], arr[i]);
			max = Math.max(max, memo[i]);
		}
		bw.write(max + "");
		
		br.close();
		bw.close();
	}
}

처음에 제출 언어 Ruby로 잘못 선택함 ㅎ,,