최 장 등차 수열 찾기

문제 설명: n 크기 의 배열 을 지정 하고 알고리즘 을 써 서 가장 긴 등차 수열 의 하위 서열 을 구 해 야 합 니 다.
우선 문 제 는 원래 배열 의 순 서 를 요구 하지 않 았 기 때문에 이 배열 을 먼저 정렬 할 수 있다.
 
1. 이 최 장 서브 시퀀스 의 요소 가 서로 인접 하 라 고 요구 하지 않 으 면 간단 한 DP 로 완성 할 수 있 습 니 다.
f [i] [j] 는 i 를 마지막 으로 하 는 특정한 하위 서열 (이 하위 서열 의 등 차 는 j) 의 최대 길 이 를 나타 낸다.
그렇게    f [i] [j] =  f [i-1] [ Num[i] - Num[j] ] +1 ,  i > 0, 이 등식 은 DP 의 전이 방정식 으로 이 알고리즘 의 복잡 도 는 O (n ^ 2) 임 이 분명 하 다.
 
코드 는 잘 쓰 여 있 습 니 다. 다만 여기 서 게 으 름 을 피 워 서 두 개의 수의 차이 의 최대 치 (즉, 위의 방정식 에서 j 의 수치 범위) 가 범위 가 있다 고 가정 한 것 입 니 다. 그래서 게 으 름 을 피 워 서 배열 로 상수 시간 내 에 찾 습 니 다. 이 가설 을 없 애 면 Vector 를 사용 한 다음 에 2 분 에 찾 거나 map 를 사용 해 야 합 니 다. 이것 은 마지막 복잡 도 는 O (n ^ 2 * logn) 입 니 다.
 

const int MAX=1010;
int dp[MAX][MAX];
int longestSubSeq(vector<int> nums)
{
	int sz=nums.size();
	if (sz <= 1) return sz;

	sort(nums.begin(),nums.end());

	int ans=1;
	int i,j;
	for(i=0;i<MAX;i++)
		for(j=0;j<MAX;j++)
			dp[i][j]=1; //    

	for(i=1;i<sz;i++)
	{
		for(j=i-1;j>=0;j--)
		{
			int diff=nums[i]-nums[j];
			dp[i][diff]=dp[j][diff]+1;
			ans=max(ans,dp[i][diff]);
		}
	}
	return ans;
}

1.2 또 다른 DP 방법 이 있 습 니 다. dp [i] [j] 는 i 에서 j 까지 의 하위 문자열 이 얻 을 수 있 는 최대 치 를 표시 합 니 다. 그러면 dp [i] [j] = max {dp [i] [k] + 1 |  nums [j] - nums [k] = nums [k] - nums [i], 그 중에서 i < k < j, i, j 의 길이 부터 계산 하면 됩 니 다. 이 방법의 복잡 도 는 O (n ^ 3) 이 고 코드 는 간단 합 니 다.

int maxSeq(vector<int>& num)
{
	int n=num.size();
	if(n<2)
		return 0;
	vector<vector<int> > dp(n,vector<int>(n,1));
	int ans=1;
	for(int i=0;i<n-1;i++)
		for(int j=i+1;j<n;j++)
		{
			int k=0;
			for(int t=0;t<i;t++)
			{
				if(num[i]-num[t]==num[j]-num[i])
					k=max(k,dp[t][i]);
			}
			dp[i][j]+=k;
			ans=max(ans,dp[i][j]);
		}
		return ans+1;
}

 
2. 하위 서열 이 연속 적 이 라면 dp [i] 로 i 로 끝 나 는 하위 문자열 이 얻 을 수 있 는 최대 길 이 를 표시 합 니 다. len [i] 이 길이 의 서열 에 대응 하 는 등 차이 점 을 표시 합 니 다.
그래서  dp [i] = dp[i-1]+1 (nums [i] - nums [i - 1] = len [i - 1]) 또는 2;