import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[][] = new int[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j <= i; j++) {
a[i][j] = sc.nextInt();
}
}
int d[][] = new int[n][n];
d[0][0] = a[0][0];
for(int i = 1; i < n; i++) {
for(int j = 0; j <= i; j++) {
d[i][j] = d[i - 1][j] + a[i][j];
if(j - 1 >= 0 && d[i][j] < d[i - 1][j - 1] + a[i][j]) {
d[i][j] = d[i - 1][j - 1] + a[i][j];
}
}
}
int answer = d[n - 1][0];
for(int i = 0; i < n; i++) {
answer = Math.max(answer, d[n - 1][i]);
}
System.out.println(answer);
}
}
어떤 수가 선택되기 전에 선택된 수는 대각선 왼쪽 위, 오른쪽 위에 있는 것이다.
D[i][j] = i행 j열이 선택되었을 때, 최대합
(i, j)가 선택되기 전에 선택된 수는 (i-1,j),(i-1,j-1)중 하나다.
=> D[i][j] = Max(D[i-1][j], D[i-1][j-1]) + A[i][j]
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[] = new int[n];
for(int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int d[] = new int[n];
for(int i = 0; i < n; i++) {
d[i] = a[i];
for(int j = 0; j < i; j++) {
if(a[j] < a[i] && d[i] < d[j] + a[i]) {
d[i] = d[j] + a[i];
}
}
}
int answer = d[0];
for(int i = 0; i < n; i++) {
answer = Math.max(answer, d[i]);
}
System.out.println(answer);
}
}
LIS 문제에서 D[i] = D[j] + 1이 아니라 합을 구하는 것이므로 D[i] = D[j] + A[i]로 바꾸기만 하면 된다.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[] = new int[n];
for(int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int d[] = new int[n];
for(int i = 0; i < n; i++) {
d[i] = 1;
for(int j = 0; j < i; j++) {
if(a[j] > a[i]) {
d[i] = Math.max(d[i], d[j] + 1);
}
}
}
int answer = d[0];
for(int i = 0; i < n; i++) {
answer = Math.max(answer, d[i]);
}
System.out.println(answer);
}
}
LIS 문제에서 a[j] a[i]를 비교하는 부등호 하나만 a[j] > a[i]로 변경해주면 된다.
D[i] = A[i]에서 끝나는 가장 긴 감소하는 부분 수열의 길이
D[i] = max(D[j]) + 1 (j < i && A[j] > A[i])
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[] = new int[n];
for(int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int d[] = new int[n];
for(int i = 0; i < n; i++) {
d[i] = 1;
for(int j = 0; j < i; j++) {
if(a[j] < a[i]) {
d[i] = Math.max(d[i] , d[j] + 1);
}
}
}
int d2[] = new int[n];
for(int i = n - 1; i >= 0; i--) {
d2[i] = 1;
for(int j = i + 1; j < n; j++) {
if(a[i] > a[j]) {
d2[i] = Math.max(d2[i], d2[j] + 1);
}
}
}
int answer = d[0] + d2[0] - 1;
for(int i = 0; i < n; i++) {
answer = Math.max(answer, d[i] + d2[i] - 1);
}
System.out.println(answer);
}
}
가장 긴 증가하는 부분 수열(D)과 가장 긴 감소하는 부분 수열(D2)를 구한 다음
D[i] = i에서 끝나는 가장 긴 증가하는 부분 수열
D2[i] = i에서 시작하는 가장 긴 감소하는 부분 수열
D[i] + D2[i] -1이 가장 큰 값을 찾으면 된다.