[백준, BOJ 11055] 가장 큰 증가 부분 수열 (java)

출처-https://www.acmicpc.net/problem/11055

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

---

728x90

 

내가 푼 방식

: '11053'번과 동일한 방식으로 품.

  dp 배열에 순서를 저장해주지 않고 합을 저장해줌.

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();
		int arr[]=new int[n+1];
		long dp[]=new long[n+1];
		
		for (int i=1;i<=n;i++)
			arr[i]=scan.nextInt();
		
		dp[1]=arr[1];
		for (int i=2;i<=n;i++) {
			for (int j=1;j<i;j++) {
				if (arr[i]>arr[j]) {
					if (dp[i]<=dp[j]+arr[i])
						dp[i]=dp[j]+arr[i];
				}
			}
			if (dp[i]==0)
				dp[i]=arr[i];
		}
		
		long max=0;
		for (int i=1;i<=n;i++) {
			if (max<=dp[i])
				max=dp[i];
		}
		
		System.out.println(max);
	}

}