백준 11055 가장 큰 증가하는 부분수열

문제보기

11053 가장 긴 증가하는 부분수열

을 참고하면 된다.

달라진 것은 하나다. 

D[i] < D[j]+1

일때 +1 의 의미는 수열의 길이가 1증가 한다는 것이다. 

여기서 +1 -> A[i]로 바꿔준다면 값들을 더하면서 증가하는 수열이 될것이다. 

package Problems;
 
/**
 * 
 * 백준 11055 LIS
 * 
 * 
 */
 
import java.util.Scanner;
 
public class Boj11055dp {
    public static int n, arr[], d[];
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
 
        n = in.nextInt();
        
        arr = new int[n];
        d = new int[n];
 
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
 
        for (int i = 0; i < n; i++) {
            d[i] = arr[i];
 
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i] && d[i] < d[j] +arr[i]) {
 
                    d[i] = d[j] + arr[i];
 
                }
            }
 
 
        }
        
        int max = d[0];
        
        for(int i = 0; i < n; i++) {
            if(max < d[i]) {
                max = d[i];
            }
        }
        
        System.out.println(max);
 
    }
 
}