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

import java.io.*;

class Main {

static int d[];

public static void main(String[] args) throws IOException {

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

int size = Integer.parseInt(in.readLine());

d = new int[size];

String[] input = in.readLine().split(" ");

int[] sequence = new int[size];

for(int i=0; i<size; ++i) {

sequence[i] = Integer.parseInt(input[i]);

}

for(int i=0; i<size; ++i) {

d[i] = sequence[i];

for(int j=0; j<i; ++j) {

if(sequence[j] < sequence[i] && d[i] < d[j] + sequence[i]) {

d[i] = d[j] + sequence[i];

}

}

}

int result = d[0];

for(int i=1; i<size; ++i) {

if(result < d[i])

result = d[i];

}

System.out.println(result);

}

}

가장 긴 증가 부분 수열에서 일부만 바꾸면 된다.

Memoization 하는 것은 입력된 수열의 해당 인덱스가 마지막 수열일 때 수열을 이루는 원소의 합이다.

길이를 계산할 때는 1을 더하였으나 합을 계산해야 하므로 입력된 수열의 해당 인덱스의 원소를 더한다.

또한 어렵다... ㅜㅠㅠ