(12) [C, C++, Java] 백준 No.11055 : 가장 큰 증가 부분 수열

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-12-DP-문제-풀이3-2-백준-No11055-가장-큰-증가-부분-수열

 

# C++

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> d(n);    
    vector<int> a(n);
    
    for (int i=0; i<n; i++)
        cin >> a[i];

    for (int i=0; i<n; i++) 
    {
        d[i] = a[i];
        for (int j=0; j<i; j++) 
        {
            if (a[j] < a[i] && d[j]+a[i] > d[i])
                d[i] = d[j]+a[i];                 // A[j] < A[i]를 만족하는 d 들 중 최대값 + a[i]이 들어감.
        }
    }
    
    cout << *max_element(d.begin(),d.end()) << '\n';
    return 0;
}

# C

#include <stdio.h>
int a[1000];
int d[1000];
int main() {
    int n;
    scanf("%d",&n);
    for (int i=0; i<n; i++) {
        scanf("%d",&a[i]);
    }
    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 ans = d[0];
    for (int i=0; i<n; i++) {
        if (ans < d[i]) {
            ans = d[i];
        }
    }
    printf("%d\n",ans);
    return 0;
}

 

# Java

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 ans = d[0];
        for (int i=0; i<n; i++) {
            if (ans < d[i]) {
                ans = d[i];
            }
        }
        System.out.println(ans);
    }
}