BOJ11053 가장 긴 부분 수열(다시보기)

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

arr[0] 부터 arr[i] 까지의 가장 긴 증가하는 부분 수열을 구하며 나아간다. (i = 0~n) 

#include <iostream>
#include <algorithm>
using namespace std;
 
int arr[1001];
int dp[1001];//dp[i] : a[i]를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이
int n;
 
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
    }
 
    int res = 0;
    for (int i = 0; i < n; i++) {
        res = max(res, dp[i]);
    }
    cout << res;
}

오답(시간초과)입니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> arr;
int dp[1001];
int n;
int result;
 
void function(int pos, int cnt) {
    if (pos >= n) return;
    
    if (dp[pos] < cnt) dp[pos] = cnt;
    result = max(result, dp[pos]);
    for (int i = pos+1; i < n; i++) {
        if (arr[pos] < arr[i]) function(i, cnt + 1);
    }
}
 
int main()
{
    cin >> n;
    int input;
    for (int i = 0; i < n; i ++ ) {
        cin >> input;
        arr.push_back(input);
    }
    function(0, 1);
    cout << result;
}