11053 최장 증가 부분 수열

#include<iostream>

using namespace std;

int n;
int main(){
        cin>>n;
        int arr[n+1];
        int d[n+1];
        arr[0]=0;
        for(int i=0; i<=n; i++)
                d[i] = 0;
        for(int i=1; i<=n; i++){
                cin>>arr[i];
        }

        int mxd = 0, mxans=0;
        for(int i=1; i<=n; i++){
                for(int j=0; j<i; j++){
                        if(arr[j]<arr[i]){
                                mxd = std::max(d[j]+1,mxd);
                        }
                }
                d[i] = mxd;
                mxd = 0;
        }

        for(int i=1; i<=n; i++){
                mxans = std::max(d[i],mxans);
        }
        cout<<mxans<<endl;

}

---

Time complexity : o(n^2)
d[i] : arr[i] 값을 수열의 마지막 값으로 가지는 수열의 길이

---

ex)
6
10 20 10 30 20 50

입력이 위와 같을 경우

배열 d의 변화

i) i==1

	d[0]	d[1]	d[2]	d[3]	d[4]	d[5]	d[6]
	0	1	0	0	0	0	0

i) i==2

	d[0]	d[1]	d[2]	d[3]	d[4]	d[5]	d[6]
	0	1	2	0	0	0	0

i) i==3

	d[0]	d[1]	d[2]	d[3]	d[4]	d[5]	d[6]
	0	1	2	1	0	0	0

i) i==4

	d[0]	d[1]	d[2]	d[3]	d[4]	d[5]	d[6]
	0	1	2	1	3	0	0

i) i==4

	d[0]	d[1]	d[2]	d[3]	d[4]	d[5]	d[6]
	0	1	2	1	3	2	0

i) i==5

	d[0]	d[1]	d[2]	d[3]	d[4]	d[5]	d[6]
	0	1	2	1	3	2	4