動的計画法によるC++の最大増分シーケンス

配列のサイズがnであり、配列のサイズがnである場合、最大増分部分のサイズを表すコード。

#include <iostream>
#include <vector>

using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    freopen("input.txt", "rt", stdin);
    int n, res=0;
    cin>>n;
    vector<int> arr(n+1), dp(n+1);
    for(int i=1; i<=n; i++){
        cin>>arr[i];
    }
    dp[1]=1;
    for(int i=2; i<=n; i++){
        int max_temp=0;
        for(int j=i-1; j>=1; j--){
            if(arr[j]<arr[i]) {
                max_temp = max(dp[j], max_temp);
            }
        }
        dp[i]=max_temp+1;
        res = max(dp[i], res);
    }
    cout<<res;
    return 0;
}

max temp=max(dp[j],max temp):最大増分数列サイズ

dp[i]=max temp+1:+1.

ex)
8
5 3 7 8 6 2 9 4