부분 삼각 수열
면접 대비시간 제한2초메모리 제한128 MB
수열에서 임의의 세 원소를 골라도 삼각형 조건을 만족하는 부분수열의 최대 길이를 구하는 문제입니다.
문제
세 수 x, y, z가 x + y > z, x + z > y, y + z > x를 모두 만족하면, 이 세 수는 삼각관계에 있다고 한다.
길이가 N인 수열 B의 서로 다른 세 위치 i, j, k에 대해 B[i], B[j], B[k]가 항상 삼각관계에 있으면, B를 삼각 수열이라고 한다.
수열 A가 주어진다. A에서 원소를 몇 개 삭제해 남은 수열이 삼각 수열이 되도록 할 때, 만들 수 있는 삼각 수열의 최대 길이를 구하시오.
입력
첫째 줄에 수열의 크기 N이 주어진다.
둘째 줄에 수열 A의 원소가 공백으로 구분되어 주어진다. N은 50 이하의 자연수이고, A의 각 원소는 10^9 이하의 자연수이다.
출력
가장 긴 부분 삼각 수열의 길이를 출력한다.