동적계획법을 이용한, 최대 부분 증가수열(LIS : Longest Increasing Subsequence) in C++

배열의 크기 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;
}

• dp[i] : i번째 원소를, 증가수열 부분의 마지막이라고 할때의, 최대 부분 증가수열의 크기
• i번째의 원소보다 작은 j의 범위에서, i번째 원소보다 작은 j번째 원소 중에, 가장 큰 부분 증가수열 크기에 +1을 한다.
• if(arr[j] < arr[i]) : i번째 원소보다 작은 j번쨰 원소 중에
• max_temp = max(dp[j], max_temp) : 가장 큰 부분 증가수열 크기에
• dp[i] = max_temp+1 : +1을 한다.

ex)
8
5 3 7 8 6 2 9 4