• Home
  • About
    • JOOS photo

      JOOS

      Joos's blog

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
  • Projects

[백준] 11055번 : 가장 큰 증가 부분 수열 with python3, cpp

25 Aug 2018

Reading time ~1 minute

https://www.acmicpc.net/problem/11055

n = int(input())
d = list(map(int, input().split()))
d.insert(0,0)
sums = [0]*(n+1)
# sums[i]는 i번쨰까지 수열중에서 가장 큰 증가하는 수열의 합이다.

for i in range(n+1):
    sums[i] = d[i]
    for j in range(i):
        if d[j] < d[i] and sums[i] < d[i] + sums[j]:
            # i번째 보다 작은 수고, 지금 sums값보다 d[i]를 포함한 sums값이 큰 게 있으면
            sums[i] = sums[j] + d[i]
            # 그걸로 바꾼다.
print(max(sums))
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i=0; i<n; i++)
        cin >> a[i];

    vector<int> d(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[j]+a[i] > d[i])
                d[i] = d[j]+a[i];

        }
    }
    cout << *max_element(d.begin(),d.end()) << '\n';
    return 0;
}


algorithm백준 Share Tweet +1