백준
가장 긴 바이토닉 수열
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int i, n = sc.nextInt();
int []a = new int[n], d = new int[n], r = new int[n];
for(i=0;i<n;i++) a[i] = sc.nextInt();
lis(a, d, n);
reverseLis(a, r, n);
System.out.println(find(d, r, n));
sc.close();
}
private static void lis(int[] a, int[] d, int n){
int i, j;
for (i = 0; i < n; i++) {
d[i] = 1;
for (j = 0; j <= i; j++)
if (a[j] < a[i] && d[i] < d[j] + 1)
d[i]++;
}
}
private static void reverseLis(int []a, int[] r, int n){
int i, j;
for (i = n - 1; i >= 0; i--) {
r[i] = 1;
for (j = n - 1; j >= i; j--)
if (a[j] < a[i] && r[i] < r[j] + 1)
r[i]++;
}
}
private static int find(int[] d, int[] r, int n){
int i, res = 0;
for(i=0;i<n;i++) if(res<d[i]+r[i]) res = d[i]+r[i];
return res-1;
}
}
개인적으로 수열 부분이 미흡한 것같다. 시간내에 풀지 못해서 풀이를 참고했다.
d[i] = i에서 끝나는 가장 긴 증가하는 부분수열과 i에서 시작하는 가장 긴 감소하는 부분 수열의 합을 구하고 그중 최댓값을 구하는 문제이다.
이문제는 다시 풀어봐야할 문제 같다. 지난 과제를 통해 비슷한 문제를 풀었는데도 다시보니 새롭다.
연속 합 2
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];
int[] d2 = new int[n]l
for (int i = 0; i < n; i++) {
d[i] = a[i];
if (i >= 1) {
if (d[i] < d[i - 1] + a[i]) {
d[i] = d[i - 1] + a[i];
}
}
}
for (int i = n - 1; i >= 0; i--) {
d2[i] = a[i];
if (i < n - 1) {
if (d2[i] < d2[i + 1] + a[i]) {
d2[i] = d2[i + 1] + a[i];
}
}
}
int ans = d[0];
for (int i = 1; i < n; i++) {
if (ans < d[i]) {
ans = d[i];
}
}
for (int i = 1; i < n - 1; i++) {
if (ans < d[i - 1] + d2[i + 1]) {
ans = d[i - 1] + d2[i + 1];
}
}
System.out.println(ans);
지난번 시간에 푼 연속 합에 조건이 추가된 문제이다.
시간내에 풀지 못해서 풀이를 참고했다.
- d[i]를 구한다. (i의 왼쪽 부분 최댓값)
- n-1 부터 d2[i]를 구한다. (i의 오른쪽 부분 최댓값)
- d[i]의 최댓값을 구한다.
- for문의 index는 1 ~ n-2까지 3번에서 구한 값과 d[i-1] + d2[i+1] 값 중 최댓값을 구한다.
다이나믹 프로그래밍은 모각코하면서 처음 접했는데 어렵다. 더 많은 문제들을 풀어봐야할 것같다.