[문제해결을 위한 창의적 알고리즘] Maximum Sum (고급, p144)

이 문제는 수열이 주어졌을때, 연속된 부분 수열의 합이 최대가 되는 값을 찾아 내는 문제이다. O(n^2)을 원하는 문제가 아니므로 점화식을 찾아내어 동적 계획법 (Dynamic Programming)으로 풀어야 하는 문제이다. 

해설에서 잘 설명하고 있지만, k번째 항목으로 끝나는 부분 수열을 만든다고 하면, k-1번째까지의 최대 합에 k번째 값을 더한 값과 k-1번째까지의 합은 버리고 k번째 항목을 비교하여 둘 중 더 큰 값을 취하면 k번째 항목으로 끝나는 부분 수열의 최대값을 구할 수 있다.

import java.util.Scanner;

public class MaxSumSol148 {

public static final int INF = 987654321;

public static int[] S = new int[100000];

public static int n, ans =-INF;

public static int[] DT = new int[100000];

public static int max(int a, int b){

return a > b ? a :b;

}

public static int f(int k){

// base case

if (k==0)

DT[k]=S[0];

// k-1번째까지의 최대값 부분 수열에 k번째 값을 더하거나 그냥 k번째 값만 취한다

else if (DT[k]==0)

DT[k]=max(DT[k-1]+S[k], S[k]);

return DT[k];

}

public static void main(String[] args){

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

for (int i =0; i< n; i++)

S[i]=sc.nextInt();

sc.close();

for (int i = 0; i < n; i++)

ans = max(ans, f(i));

System.out.println(ans);

return;

}

}

Big O(n)

Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/MaxSumSol148.java

문제해결을 위한 창의적 알고리즘 목록