[BOJ 11055 // C++] 가장 큰 증가 부분 수열

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1991번 문제인 트리 순회이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11055

11055번: 가장 큰 증가 부분 수열

이 문제는 증가 부분 수열 가운데 각 항의 총합이 가장 큰 부분 수열을 찾는 문제이다.

수열을 구성하는 수는 모두 1000 이하의 양의 정수이므로, 크기 1000짜리 배열을 만들어 숫자가 들어올 때마다 배열의 해당 숫자번째 원소를 그 수로 끝나는 부분수열 중 합이 최대인 경우로 갱신해나가주면 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;

int nums[1001];

int main()
{
    int N; cin >> N;
    int x;
    for (int _ = 0;_ < N;_++) {
        cin >> x;
        if (nums[x] < x) nums[x] = x;
        for (int i = x - 1; i >= 0;i--) {
            if (nums[i] + x > nums[x]) nums[x] = nums[i] + x;
        }
    }
    int ans = 0;
    for (int i = 0;i <= 1000;i++) {
        if (ans < nums[i]) ans = nums[i];
    }
    cout << ans;

    return 0;
}