가장 큰 증가 부분 수열:11055번 - JAVA

---

1.문제 링크

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

11055번: 가장 큰 증가 부분 수열

---

2. 문제 설명

---

3. 문제 접근

과정 요약

1.  arr[idx]값을 dp[idx]에 추가한다. (dp[idx] = arr[idx])

2.  dp 값이 다음 조건이 일치할 경우에 변경한다.

(1) arr[left] < arr[right]

(2) dp[right] < dp[left] + arr[right]

 

두 조건 만족 시, dp[right] = dp[left] + arr[right]

 

표를 이용한 에제 설명은 추후에...ㅎㅎ

---

4. 문제 풀이

 

package dp1_practice;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class most_biggiest_subsequence {
    static int [] arr;
    static int [] dp;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        
        int max = 0;
        arr = new int[n+1];
        dp = new int[n+1];
        
        for (int idx = 1; idx <= n; idx++) {
            arr[idx] = Integer.parseInt(st.nextToken());
        }
        
        for (int right = 1; right <= n; right++) {
            dp[right] = arr[right];
            for (int left = 1; left < right; left++) {
                if(arr[left] < arr[right] && dp[right] < dp[left] + arr[right])    
                    dp[right] = dp[left] + arr[right];
            }
        }
        
        for (int idx = 1; idx <= n; idx++)
            if(max < dp[idx])    max = dp[idx];
        
        System.out.println(max);
        
        br.close(); 
    }
}
 

<정답 확인>

---