백준 1912번 - 연속합

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

1912번: 연속합

 

---

다음 문제를 푸는 방식은 다음과 같다.

다음 예제처럼 수열이 존재할 때 

왼쪽부터 수를 비교하여 연속되는 수의 합의 모든 경우의 수를 dp 라는 배열 안에 삽입한 뒤 dp 배열 중 최댓값을 찾으면 된다.

 

10 > -4 이기 때문에 

두 수를 더한 6을 dp[1]에 저장

 

10+(-4) > 3 이기 때문에

세 개의 수를 더한 9를 dp[2]에 저장

 

10+(-4)+3 > 1 이기 때문에

네 개의 수를 더한 10을 dp[3]에 저장

...

그리고 -14 < 12 이기 때문에 

12부터 다시 시작한다. 

 

이렇게 해서 다음과 같은 식이 나온다.

 

 

 

그러면 다음과 같은 dp 배열이 완성되고 이 배열 중 최댓값인 33이 답이 된다.

 

 

코드(bottom-up 방식)

import java.io.*;
import java.util.*;

public class Main{
	
	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
	    int N = sc.nextInt();
	    int arr[] = new int[N];
	    int dp[] = new int[N];
	    
	    for(int i=0;i<N;i++)
	    {
	    	arr[i]=sc.nextInt();
	    }
	    
	    dp[0]=arr[0];
	    int max=dp[0];
	    
	    for(int i=1;i<N;i++)
	    {
	    	dp[i]=Math.max(dp[i-1]+arr[i], arr[i]);
	    	max = Math.max(max, dp[i]);
	    }
	    System.out.println(max);
	}
}

 

 

코드(top-down 방식)

import java.io.*;
import java.util.*;

public class Main{
    static int arr[];
    static int dp[];
	static int max;
  
    public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
	    int N = sc.nextInt();
	    
	    arr = new int[N];
	    dp = new int[N];
	    for(int i=0;i<N;i++)
	    {
	    	arr[i]=sc.nextInt();
	    }
	   
	    dp[0]=arr[0];
	    max=arr[0];
	    
	    recur(N-1);
	    
	    System.out.println(max);
	}  
    
    static int recur(int N)
    {
    	if(dp[N]==0)
    	{
    		dp[N]=Math.max(recur(N-1)+arr[N], arr[N]);
    		max = Math.max(dp[N], max);
    	}
    	return dp[N];
    }
}