백준 1912. 연속합(Kadane의 알고리즘)

https://www.acmicpc.net/problem/1912

 

나의 풀이 1번

(동적 프로그래밍으로 풀어 봤으나, 부분합을 구하는 알고리즘에서 O(N^2)의 시간복잡도가 발생하여 시간초과)

package test;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class test117 {
	static int N;
	static int[] nums;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = Integer.parseInt(br.readLine());
		nums = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}

		bw.write(String.valueOf(findPartialSum(N - 1)));
		bw.flush();
		bw.close();
		br.close();
	}

	static int findPartialSum(int N) {
		int max = Integer.MIN_VALUE;
		int[] dp = new int[N + 1];
		if (N == 1)
			return nums[0];
		dp[0] = 0;
		for (int i = 1; i <= N; i++) {
			dp[i] = nums[i - 1] + dp[i - 1];
			max = Math.max(max, dp[i]);
			int[] partialDp = new int[i + 1];
			for (int j = 1; j < i; j++) {
				max = Math.max(max, dp[i] - dp[j]);
			}
		}

		return max;
	}
    }

 

두 번째 풀이

(Kadane의 알고리즘으로 최적해를 유지하면서 진행, 처음부터 dp[i]를 최적의 부분합으로 정해 놓고 진행하니까 알고리즘이 단순화됨)

package test;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class test117 {
	static int N;
	static int[] nums;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = Integer.parseInt(br.readLine());
		nums = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}

		bw.write(String.valueOf(findPartialSum(N - 1)));
		bw.flush();
		bw.close();
		br.close();
	}

	static int findPartialSum(int N) {
		int[] dp = new int[N+1]; 
        int max = Integer.MIN_VALUE; // 누수 방지를 위해 지역변수로 선언

		dp[0] = nums[0];
		max = Math.max(max, dp[0]);

		for (int i = 1; i <= N; i++) {
			dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]); // 이전 값과 비교하여 갱신
			max = Math.max(max, dp[i]); // 최대값 갱신
		}

		return max;
	}

}

 

 

Kadane's Algorithm에 대한 간단한 설명:

https://medium.com/@vdongbin/kadanes-algorithm-%EC%B9%B4%EB%8D%B0%EC%9D%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-acbc8c279f29