Q11055. 가장 큰 증가 수열

현재 숫자를 이후 숫자들에 더하며 나아가는 로직

로직 설명을 해야하는데 어렵네요.

i번째 숫자를 i+2번째에 더했다고 가정할때,

"i번째 숫자 < i+k번째 숫자 < i+2번째" 숫자여야 합니다.

"i+k번째 숫자 < i+2번째 숫자"라는 조건이 없을 경우

"i번째 숫자"가 중복으로 더해지는 문제가 발생하기 때문입니다.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q11055 { static long[][] array = new long[2][1001]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int num = Integer.valueOf(st.nextToken()); st = new StringTokenizer(br.readLine()); for (int i = 1; i <= num; i++) { array[0][i] = Integer.valueOf(st.nextToken()); array[1][i] = array[0][i]; } long max = array[0][1]; array[1][1] = array[0][1]; for (int i = 1; i < num; i++) { long nowNum = array[0][i]; long nowValue = array[1][i]; long inputNum = 0; for (int j = i+1; j <= num; j++) { if (nowNum < array[0][j]) { if (inputNum == 0 || inputNum > array[0][j]) { long tempSum = nowValue + array[0][j]; if (tempSum > array[1][j]) { array[1][j] = tempSum; if (max == 0 || max < tempSum) { max = tempSum; } } } } } } System.out.println(max); } }