문제 해결 전략

: LIS 와 동일한 문제이고,

• LIS를 작성하고 변경하자.

생각해보기.

• 0번 인덱스를 기준으로 해서 오른쪽으로 진행했을 때가 가장 긴 증가 수열일 수 있다.

• 1번 인덱스를 기준으로 해서 오른쪽으로 진행했을 때가 가장 긴 증가 수열일 수 있다.

• 2번 인덱스를 기준으로 해서 오른쪽으로 진행했을 때가 가장 긴 증가 수열일 수 있다.

-> 왜냐하면 0번이나 1번이 2번보다 클 수 있다면 다음 번호 선택시 최대 개수 나올 수 있다.
: MAIN 문에서 타겟번호 설정해서 돌려야 한다.

---

재귀 함수.

• idx 번호를 선택해서 다음 번 번호와 비교하는 코드를 작성해야 한다.

-> for문을 작성한 이유는 바로 다음번 번호를 선택하는 것 뿐 아니라 , +2 , + 3 다음의 인덱스를 선택할 때도 있기 때문이다.

• for문이 있기 때문에 max(go(i) , refV); // 선택하지 않는 방법 의 코드는 필요 없다!
  

시간 복잡도

: n이 1000개이기 때문에 재귀가 아닌 탑다운을 선택함.