[BaekjoonオンラインJudge]11053-最長成長部分数列

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

アルゴリズム分類

ダイナミックプログラミング

質問する

数列Aが与えられると、最も長い部分の数列を求めるプログラムが作成される.
例えば、A={10,20,10,30,20,50}を数える場合、最も長くなる部分はA={10,20,10,30,20,50}であり、長さは4である.

入力

第1行は、数列AのサイズN(1≦N≦1000)を与える.
2行目は、数列Aを構成するAiを与える.(1 ≤ Ai ≤ 1,000)

しゅつりょく

第1行出力数列Aの最長増分部分数列の長さ.

入力例1

6
10 20 10 30 20 50

サンプル出力1

4

Solve

Idea

数列Aのすべての数については、数で終わる最長部分の数列の長さが格納される.それらの長さのうち最も長い値は、数列Aの最も長い部分の数列の長さである.
数列Aに任意の数bを加えると、bより小さい数列のうち、数で終わる最長部分の数列の長さが最も長い場合が見つかる.その長さにbで終わる最長部分数列の長さを加える.数列Aの最長増分部分数列の長さは同様に求めることができる.

Full Code

#include <iostream>

using namespace std;

int main()
{
    int n; // length of original sequence
    cin >> n;

    // allocate memory for original sequence
    pair<int, int> *seq = new pair<int, int>[n]; // pair <number, length of the longest partial sequence which ends with the number>

    // get input
    for (int idx = 0; idx < n; idx++)
    {
        int number;
        cin >> number;
        seq[idx] = pair<int, int>(number, 0);
    }

    // calculate length of the longest partial sequence which ends with each number
    for (int idx = 0; idx < n; idx++)
    {
        int length = 0;

        for (int sub_idx = 0; sub_idx < idx; sub_idx++)
        {
            if (seq[sub_idx].first < seq[idx].first)
            {
                length = max(length, seq[sub_idx].second);
            }
        }

        seq[idx].second = length + 1;
    }

    // calculate length of the longest partial sequence of original sequence
    int length = 0;
    for (int idx = 0; idx < n; idx++)
    {
        length = max(length, seq[idx].second);
    }

    // print result
    cout << length;

    // free memory for original sequence
    delete[] seq;

    return 0;
}