백준 11055번 가장 큰 증가하는 부분 수열 [JAVA]

문제

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

 

 

 

 

이번에는 가장 긴 증가하는 수열(LIS)를 구하는것인 아니라 증가하는 수열의 합이 가장 큰 경우를 출력하는 문제이다 

 

11053번 가장 긴 증가하는 부분 수열 문제에서 코드를 조금만 수정하면 된다

 

 

알고리즘 설계

 

가장 긴 증가하는 부분 수열을 구할떄는 길이를 구해야 했으므로 

길이가 커질때마다 +1을 해주는식으로

각 위치를 기준으로 형성되는 증가하는 부분 수열중에서 가장 긴 길이를 dp배열에 저장했다면

 

 

가장 큰 증가하는 부분 수열은 가장 긴게 중요한게 아니라 

증가하는 부분 수열의 합이 가장 큰 경우를 구하는것이므로 

증가하는 수열 일때마다 그 값을 더해주는 식으로 

각 위치를 기준으로 형성되는 증가하는 부분 수열중에서 가장 큰 값을 dp배열에 저장하면 된다 

 

역시 LIS 유형 문제는 말로 설명하기가 어렵다 

 

 

 

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int []list=new int[n]; //값을 넣어준다
        int []dp=new int[n]; //현재위치의 수로 끝나는 증가하는 부분 수열중에 최댓값 저장
        for(int i=0;i<n;i++){
            list[i]=sc.nextInt();
        }

        dp[0]=list[0];

        for(int i=1;i<n;i++){
            dp[i]=list[i];
            for(int j=0;j<i;j++){
                  if(list[i]>list[j] && dp[j]+list[i]>dp[i])
                      dp[i]=dp[j]+list[i];
                }
            }

        int max=0;
        for(int i=0;i<n;i++){
            if(max<dp[i])
                max=dp[i];
        }

        System.out.print(max);


    }
}